Submission #798070

#	Time	Username	Problem	Language	Result	Execution time	Memory
798070		aymanrs	Raisins (IOI09_raisins)	C++14	100 / 100	92 ms	24788 KiB

raisins

    #include<bits/stdc++.h>
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
    using namespace std;
    void solve(){
    	int n, m;
    	cin >> n >> m;
    	int dp[n][m][n][m];
    	int pr[n][m];
    	for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) {
    		cin >> pr[i][j];
    		dp[0][0][i][j] = 0;
    		if(i) pr[i][j] += pr[i-1][j];
    		if(j) {
    			pr[i][j] += pr[i][j-1];
    			if(i) pr[i][j] -= pr[i-1][j-1];
    		}
    	}
    	for(int h = 0;h < n;h++){
    		for(int w = h ? 0 : 1;w < m;w++){
              #pragma GCC ivdep
    			for(int i = 0;i+h < n;i++){
                  #pragma GCC ivdep
    				for(int j = 0;j+w < m;j++){
    					dp[h][w][i][j] = pr[i+h][j+w]-(i ? pr[i-1][j+w] : 0)-(j ? pr[i+h][j-1] : 0)+(i&&j ? pr[i-1][j-1] : 0);
    					int x = INT_MAX;
    					for(int k = 0;k < h;k++) x = min(x, dp[k][w][i][j]+dp[h-k-1][w][i+k+1][j]);
    					for(int k = 0;k < w;k++) x = min(x, dp[h][k][i][j]+dp[h][w-k-1][i][j+k+1]);
    					dp[h][w][i][j] += x;
    				}
    			}
    		}
    	}
    	cout << dp[n-1][m-1][0][0] << '\n';
    }
    int main(){
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	solve();
    }

• Subtask 1: 100 / 100