Submission #1336909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1336909		iq500	Grid Coloring (JOI25_ho_t1)	C++20	45 / 100	118 ms	3532 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fir first
#define sec second
using namespace std;

signed main(){
    int n; cin>>n;
    if(n<=500){
        int a[n], b[n], g[n][n];
        memset(g, 0, sizeof(g));
        map<int, int> mp;
        for(int i=0; i<n; i++){
            cin>>a[i];
            g[i][0]=a[i];
            mp[a[i]]++;
        }
        for(int i=0; i<n; i++){
            cin>>b[i];
            g[0][i]=b[i];
            mp[b[i]]++;
        }
        mp[a[0]]--;
        for(int i=1; i<n; i++){
            for(int j=1; j<n; j++){
                g[i][j]=max(g[i-1][j], g[i][j-1]);
                mp[g[i][j]]++;
            }
        }
        /*for(int i=0; i<n; i++){
            for(int j=0; j<n; j++) cout<<g[i][j]<<" ";
                cout<<"\n";
        }*/
        int col=0, mx=0;
        for(auto it=mp.begin(); it!=mp.end(); it++){
            int ccol=(*it).fir, cval=(*it).sec;
            //cout<<ccol<<" "<<cval<<"\n";
            if(mx<cval){
                mx=cval;
                col=ccol;
            }
            else if(mx==cval){
                col=max(col, ccol);
            }
        }
        cout<<col<<" "<<mx;
    }
    else{
        int a[n], b[n], la=n, lb=n, bi=0, ik=0;
        for(int i=0; i<n; i++){
            cin>>a[i];
            if(a[i]==1) bi++;
            else{
                ik++;
                if(la==n && i!=0) la=i;
            }
        }
        for(int i=0; i<n; i++){
            cin>>b[i];
            if(b[i]==1) bi++;
            else{
                ik++;
                if(lb==n && i!=0) lb=i;
            }
        }
        if(a[0]==1) bi--;
        else ik--;

        int ttl=(n-1)*(n-1), dec=(la-1)*(lb-1);
        bi+=dec; ik+=(ttl-dec);
        if(ik>=bi) cout<<2<<" "<<ik<<"\n";
        else cout<<1<<" "<<bi<<"\n";

    }
    
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25
• Subtask 6: 0 / 30