Submission #386957

#	Time	Username	Problem	Language	Result	Execution time	Memory
386957		peijar	Sails (IOI07_sails)	C++17	55 / 100	25 ms	1912 KiB

sails

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAX = 1e5+1;

int nbAHauteur[MAX];
int nbPeutSurHauteur[MAX];

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbPoteaux;
	cin >> nbPoteaux;
	int nbRestants(0);
	for (int iPoteau = 0; iPoteau < nbPoteaux; ++iPoteau) 
	{
		int hauteur, aMettre;
		cin >> hauteur >> aMettre;
		nbAHauteur[hauteur]++;
		nbRestants += aMettre;
		nbPeutSurHauteur[hauteur] += aMettre;
	}

	int sol(0);
	int nbPoteauxDispo = 0;
	int nbDrapeauxDispo = 0;
	for (int iHauteur(MAX-1); iHauteur; --iHauteur)
	{
		nbPoteauxDispo += nbAHauteur[iHauteur];
		nbDrapeauxDispo += nbPeutSurHauteur[iHauteur];

		int moy = (nbRestants + iHauteur - 1) / iHauteur;
		int placeEtage = min({moy, nbPoteauxDispo, nbDrapeauxDispo});
		nbDrapeauxDispo -= placeEtage;
		nbRestants -= placeEtage;
		sol += placeEtage * (placeEtage - 1) / 2;
	}
	assert(!nbRestants);
	cout << sol << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10