oj.uz

Submission #563265

# Submission time Handle Problem Language Result Execution time Memory
563265 2022-05-16T16:46:14 Z karon Sails (IOI07_sails) C++14
40 / 100
 1000 ms 7284 KB 
#include <bits/stdc++.h>
#define pb push_back
#define rs resize
#define debug printf("Hello\n")
#define Pi 3.141592653589793 
#define sz(a)                 ll((a).size()) 
#define all(x)                (x).begin(), (x).end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
#define mp make_pair
#define f first
#define s second
#define vt vector
#define rst(a,b) memset((a),(b), sizeof(a))
#define FOR(a, b, c) for (ll a = (b); (a) <  (c); ++(a))
#define FORE(a, b, c) for (ll a = (b); (a) <= (c); ++(a))
#define FORR(a, b, c) for (ll a = (b); (a) >= (c); --(a))
#define umap unordered_map
#define len(a) (a).length()
#define pqueue priority_queue
 
using namespace std;
using vi = vector<int>;    
using ui = unsigned int;                
using ll = long long;                    
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;          
using pii = pair<int, int>;

const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
const char dir[4] = {'R', 'L', 'U', 'D'};
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;




void solve(){
	ll n;cin >> n;
	vt<pll> arr(n);
	FOR(i,0,n){
		ll a,b;cin >> a >> b;
		arr[i] = mp(a,b);
	}
	sort(all(arr));
	priority_queue<pll, vt<pll>, greater<pll>> q;
	ll t = arr[0].s;
	FOR(i,0,arr[0].f){
		if(t-->0)q.push(mp(1,i));
		else q.push(mp(0,i));
	}
	ll h = arr[0].f;
	FOR(i,1,n){
		ll tmp = arr[i].s;
		vt<pll> toadd;
		if(q.size() < arr[i].f){
			FOR(j,q.size(),arr[i].f){
				q.push(mp(0,j));
			}
		}
		while(tmp--){
			pll ff = q.top();
			q.pop();
			toadd.pb(mp(ff.f+1, ff.s));
		}
		for(auto x : toadd)q.push(x);
	}
	ll sum = 0;
	while(!q.empty()){
		ll ff = q.top().f;
		sum += (ff-1)*(ff)/2;
		q.pop();
	}
	cout << sum << endl;

}


int main(){
	fastio;

#ifndef ONLINE_JUDGE

#endif

	solve();

}

Compilation message

sails.cpp: In function 'void solve()':
sails.cpp:59:15: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long long int, long long int>, std::vector<std::pair<long long int, long long int> >, std::greater<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |   if(q.size() < arr[i].f){
      |               ^
sails.cpp:55:5: warning: unused variable 'h' [-Wunused-variable]
   55 |  ll h = arr[0].f;
      |     ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 11 ms 368 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 592 KB Output is correct
2 Correct 311 ms 2532 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 1408 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 1085 ms 1432 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 1058 ms 2168 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 1076 ms 7284 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 1077 ms 3216 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 1091 ms 3692 KB Time limit exceeded
2 Halted 0 ms 0 KB -