oj.uz

Submission #117606

# Submission time Handle Problem Language Result Execution time Memory
117606 2019-06-16T18:26:51 Z KieranHorgan Sails (IOI07_sails) C++17
70 / 100
 1000 ms 2636 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
// #define int long long
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 1000000007;

int doneUpTo[100005];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long seed;
	asm("rdtsc" : "=A"(seed));
	srand(seed);

	int n;
	cin >> n;
	// n=100000;
	int total = 0;
	int mx = 0;
	vector<pair<int,int>> listOfHeights;
	for(int i = 0; i < n; i++) {
		int H, K;
		cin >> H >> K;
		// H=K=min(i+1, 750);
		listOfHeights.push_back({H,K});
	}
	sort(listOfHeights.begin(), listOfHeights.end());
	int differentHeights = 1;
	for(int i = 1; i < n; i++)
		if(listOfHeights[i].first != listOfHeights[i-1].first)
			differentHeights++;

	long long ans = 0;
	vector<int> doneUpToVec;
	for(auto &x: listOfHeights) {
		int H = x.first;
		int K = x.second;

		// cerr << H << " " << K << ": " << endl;
		if(differentHeights <= 700) {
			while(K) {
				int j = doneUpToVec.rend() - lower_bound(doneUpToVec.rbegin(), doneUpToVec.rend(), H);
				if(j == doneUpToVec.size()) doneUpToVec.push_back(0);
				int Temp = min(H - doneUpToVec[j], K);
				ans += j*Temp;
				K -= Temp;
				doneUpToVec[j] += Temp;
				H -= Temp;
			}
		} else {
			for(int j = 0; K > 0; j++) {
				int Temp = min(H - doneUpTo[j], K);
				ans += j*Temp;
				K -= Temp;
				doneUpTo[j] += Temp;
				H -= Temp;
			}
		}
		// for(int j = 0; doneUpTo[j]; j++){
			// for(int k = 0; k < doneUpTo[j]; k++)
				// cerr << "*";
			// cerr << endl;
		// }
		// cerr << ans << endl;
	}
	cout << ans << endl;
}

Compilation message

sails.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
sails.cpp: In function 'int main()':
sails.cpp:53:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(j == doneUpToVec.size()) doneUpToVec.push_back(0);
        ~~^~~~~~~~~~~~~~~~~~~~~
sails.cpp:28:6: warning: unused variable 'total' [-Wunused-variable]
  int total = 0;
      ^~~~~
sails.cpp:29:6: warning: unused variable 'mx' [-Wunused-variable]
  int mx = 0;
      ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 512 KB Output is correct
2 Correct 647 ms 1364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 1272 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 1652 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 2428 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 1070 ms 2592 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 1014 ms 2636 KB Time limit exceeded
2 Halted 0 ms 0 KB -