oj.uz

Submission #223695

# Submission time Handle Problem Language Result Execution time Memory
223695 2020-04-16T05:38:03 Z FieryPhoenix Sails (IOI07_sails) C++11
40 / 100
 1000 ms 2284 KB 
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N,H[100001],K[100001];
int cnt[100001];

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  cin>>N;
  vector<pair<int,int>>v;
  for (int i=0;i<N;i++){
    cin>>H[i]>>K[i];
    v.push_back({H[i],K[i]});
  }
  sort(v.begin(),v.end());
  for (int i=0;i<N;i++){
    /*
    cout<<"SAIL "<<i<<": "<<v[i].first<<' '<<v[i].second<<endl;
    for (int i=0;i<=10;i++)
      cout<<cnt[i]<<' ';
    cout<<endl;
    */
    int pre=0;
    if (i>0) pre=v[i-1].first;
    cnt[0]+=v[i].first-pre;
    int k=v[i].second;
    deque<pair<int,int>>did;
    for (int j=0;;j++){
      if (cnt[j]>=k){
	did.push_front({j,k});
	k=0;
	break;
      }
      else{
	did.push_front({j,cnt[j]});
	k-=cnt[j];
      }
    }
    for (auto it:did){
      cnt[it.first]-=it.second;
      cnt[it.first+1]+=it.second;
    }
  }
  ll ans=0;
  for (ll i=1;i<=100000;i++){
    ll num=cnt[i];
    ans+=num*(i*(i-1))/2;
  }
  cout<<ans<<endl;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 384 KB Output is correct
2 Correct 6 ms 404 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 512 KB Output is correct
2 Execution timed out 1095 ms 1424 KB Time limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 1148 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 1608 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 2028 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 1086 ms 2284 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 1096 ms 2104 KB Time limit exceeded
2 Halted 0 ms 0 KB -