Submission #117605

#	Time	Username	Problem	Language	Result	Execution time	Memory
117605		KieranHorgan	Sails (IOI07_sails)	C++17	0 / 100	1081 ms	1724 KiB

sails

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

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