[BJOI2019] Row of opinion

Title Description

Small C Playing a game of arranging troops . There are... In the game $n$ A castle , In each game, two players compete for these castles . Each player has $m$ soldiers , You can go to the third party $i$ The castle sent $a_i$ Soldiers went to fight for the castle , So that the total number of soldiers does not exceed $m$.

If a player to the second $i$ The number of soldiers sent by the castle Strictly More than twice the number of soldiers sent by the opponent , Then this player will occupy the castle , get $i$ branch .

Now small C About to work with others $s$ Two players fight in pairs , this $s$ The plan of sending soldiers in the battle must be the same . Small C I learned about others through some ways $s$ The strategy that a player will use , He wants to know what strategies he should use to maximize his total score .

Because the answer may not be unique , You just need to output small C The maximum total score .

Input format

The first line of input contains three positive integers $s,n,m$, Except for small C Number of players other than 、 Number of castles and soldiers per player .

Next $s$ That's ok , Each row $n$ Nonnegative integers , Represents a player's strategy , Among them the first $i$ Number $a_i$ Indicates that this player is going to the $i$ The number of soldiers sent by the castle .

Output format

Output a non negative integer on a line , It means small C Maximum score obtained .

Examples #1

The sample input #1

1 3 10
2 2 6

Sample output #1

3

Examples #2

The sample input #2

2 3 10
2 2 6
0 0 0

Sample output #2

8

Tips

Examples 1 explain ：
Small C The best strategy is to $1$ Castle and $2$ Each castle is dispatched $5$ soldiers .

Data range ：*

about $100\%$ The data of ：
$1\le s\le 100$
$1\le n\le 100$
$1\le m\le 20000$
For every player $a_i\ge 0$,$\sum _{i=1}^n{a}_i\le m$

Learned some details of grouping backpacks .

For grouped knapsack boards .

First cycle the items , Volume , Finally, group decision .

for(int i=0;i<n;i++){
    
    for(int j=m;j>=0;j--){
     //  Want to have j>=0
        for(int k=0;k<s[i];k++){
        //for(int k=s[i];k>=1;k--) It's fine too 
            if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
        }
    }
}

Empathy , castle , Volume , grouping ; At first, I was in the wrong order , It's always been wrong .

fo(j,1,n){
    
    for(int k=m;k>=0;k--){
    
        fo(i,1,s){
    
            if(k-2*a[j][i]-1>=0)
                f[k] = max(f[k],f[k-2*a[j][i]-1]+i*j);
        }
    }
}	

int s,n,m;
int f[20010];// Just use m The maximum of 
/*  this  s  The plan of sending soldiers in the battle must be the same . */
void solve(){
    
	cin>>s>>n>>m;
	vector<vector<int>>a(n+1,vector<int>(s+1));
	fo(i,1,s){
    
		fo(j,1,n){
    
			cin>>a[j][i];
		}
	}
	fo(i,1,n){
    
		sort(all(a[i]));
	}
    fo(j,1,n){
    
    	for(int k=m;k>=0;k--){
    
    		fo(i,1,s){
    
            	if(k-2*a[j][i]-1>=0)
                f[k] = max(f[k],f[k-2*a[j][i]-1]+i*j);
        	}
        }
    }	
	//  Wrong enumeration 
    // fo(j,1,n){
    
        // fo(i,1,s){
    
            // for(int k=m;k>=0;k--){
    
            	// if(k-2*a[j][i]-1>=0)
                // f[k] = max(f[k],f[k-2*a[j][i]-1]+i*j);
            // }
        // }
    // }
    cout<<f[m]<<endl;
}

int main(){
    
    solve();
    return 0;
}

There is also a problem that may make the snake superfluous ： The total number of soldiers does not exceed m , So the state definition is no more than , It cannot be exactly equal to .