Submission #1031626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031626		ezzzay	Raisins (IOI09_raisins)	C++14	20 / 100	3 ms	776 KiB

raisins

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e3;
#define int long long
signed main(){
    int n,m;
    cin>>n>>m;
    multiset<pair<int, vector<vector<int> > > >st;
    vector< vector<int>>h(n);
    int s=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int a;
            cin>>a;
            s+=a;
            h[i].pb(a);
        }
    }
    st.insert({-s,h});
    int cmp=1;
    int ans=0;
    
    while(cmp!=n*m){
       
        
        vector< vector<int>> v= (*st.begin()).ss;
        int y=v.size();
        int x=v[0].size();
        if(x*y==1){
            st.erase(st.begin());
            continue;
        }
        bool u=0;
        int h=INT_MAX;
        int z=-1;
        
        for(int i=1;i<y;i++){
            int a=0,b=0;
            for(int l=0;l<i;l++){
                for(int k=0;k<x;k++){
                    a+=v[l][k];
                }
            }
            for(int l=i;l<y;l++){
                for(int k=0;k<x;k++){
                    b+=v[l][k];
                }
            }
            if(abs(a-b)<h){
                u=1;
                h=abs(a-b);
                z=i;
            }
        }
        
        
        for(int i=1;i<x;i++){
            int a=0,b=0;
            for(int l=0;l<i;l++){
                for(int k=0;k<y;k++){
                    a+=v[k][l];
                }
            }
            for(int l=i;l<x;l++){
                for(int k=0;k<y;k++){
                    b+=v[k][l];
                }
            }
            if(abs(a-b)<h){
                u=0;
                h=abs(a-b);
                z=i;
            }
        }
       
        if(u){
            vector< vector<int> > ta(z),tb(y-z);
            int a=0,b=0;
            for(int i=0;i<z;i++){
                for(int j=0;j<x;j++){
                    ta[i].pb(v[i][j]);
                    a+=v[i][j];
                }
            }
            
            for(int i=z;i<y;i++){
                for(int j=0;j<x;j++){
                    tb[i-z].pb(v[i][j]);
                    b+=v[i][j];
                }
            }
           
            ans+=a+b;
            st.erase(st.begin());
            st.insert({-a,ta});
            st.insert({-b,tb});
           
            cmp++;
        }
        else{
            vector< vector<int> > ta(y),tb(y);
            int a=0,b=0;
            for(int i=0;i<y;i++){
                for(int j=0;j<z;j++){
                    ta[i].pb(v[i][j]);
                    a+=v[i][j];
                }
            }
            for(int i=0;i<y;i++){
                for(int j=z;j<x;j++){
                    tb[i].pb(v[i][j]);
                    b+=v[i][j];
                }
            }
            ans+=a+b;
            cmp++;
            st.erase(st.begin());
            st.insert({-a,ta});
            st.insert({-b,tb});
           
        }
        
    }
    cout<<ans;
}

• Subtask 1: 20 / 100