Submission #563265

#	Time	Username	Problem	Language	Result	Execution time	Memory
563265		karon	Sails (IOI07_sails)	C++14	40 / 100	1091 ms	7284 KiB

sails

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 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