Submission #874869

#	Time	Username	Problem	Language	Result	Execution time	Memory
874869		josanneo22	Sails (IOI07_sails)	C++17	30 / 100	1099 ms	15956 KiB

sails

/*
Problem: IOI 2007 Sails
When:    2023-11-16 14:54:19
Author:  Ning07
*/

#include<bits/stdc++.h>
using namespace std;
using i64=long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int N; cin>>N;
    vector<int> flags(N),height(N);
    multiset<pair<i64,int>> S;//first = number of flags on row, row id
    int mh=0; vector<int> mx(2e5+500);
    for(int i=0;i<N;i++){
        cin>>height[i]>>flags[i];
        mh=max(mh,height[i]);
        mx[1]++; mx[height[i]+1]--;
    }
    for(int i=1;i<=mh;i++) mx[i]+=mx[i-1];
    // for(int i=1;i<=mh;i++) cout<<mx[i]<<' ';
    //     cout<<'\n';
    for(int i=1;i<=mh;i++) if(mx[i]!=0) S.insert(make_pair(0,i));
    vector<int> ord(N);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int x,int y){
        return height[x]<height[y];
    });
    for(int p=0;p<N;p++){
        int i=ord[p];
        multiset<pair<i64,int>> copy;
        int cnt=flags[i];
        // cout<<"cnt: " << cnt<<'\n';
        // cout<<"step " << i <<" has S: ";
        // for(auto &v:S) cout<<"{ "<<v.first<<", "<<v.second<<"}"<<' ';
        // cout<<'\n';
        for(auto&v:S){
            if(v.second>=height[i]+1) copy.insert(make_pair(v.first,v.second));
            else if(mx[v.second]==v.first) copy.insert(make_pair(v.first,v.second));
            else if(cnt) {
                cnt--;
                copy.insert(make_pair(v.first+1,v.second));
            }
            else copy.insert(make_pair(v.first,v.second));
        }
        swap(S,copy);
    }
    // cout<<"final step has S: ";
    // for(auto &v:S) cout<<"{ "<<v.first<<", "<<v.second<<"}"<<' ';
    // cout<<'\n';
    i64 ans=0;
    for(auto &v:S){
        ans+=(v.first)*(v.first-1)/2;
    }
    cout<<ans<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10