oj.uz

Submission #874869

# Submission time Handle Problem Language Result Execution time Memory
874869 2023-11-18T02:24:34 Z josanneo22 Sails (IOI07_sails) C++17
30 / 100
 1000 ms 15956 KB 
/*
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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 19 ms 1116 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 2000 KB Output is correct
2 Execution timed out 1020 ms 13488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 4952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 5468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 8528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 15412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1031 ms 15696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 15956 KB Time limit exceeded
2 Halted 0 ms 0 KB -