oj.uz

Submission #1031626

# Submission time Handle Problem Language Result Execution time Memory
1031626 2024-07-23T02:50:42 Z ezzzay Raisins (IOI09_raisins) C++14
20 / 100
 3 ms 776 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Correct 1 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 1 ms 344 KB Output isn't correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Incorrect 1 ms 604 KB Output isn't correct
14 Incorrect 2 ms 348 KB Output isn't correct
15 Incorrect 2 ms 604 KB Output isn't correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Incorrect 2 ms 600 KB Output isn't correct
19 Correct 3 ms 604 KB Output is correct
20 Incorrect 3 ms 776 KB Output isn't correct