Submission #1170061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170061		miniob	Naan (JOI19_naan)	C++20	24 / 100	1 ms	328 KiB

naan

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

int war[2007][2007];
int pref[2007][2007];
int potrz[2007];
bool czy_juz[2007];
int gdzie_jestem[2007];

int nastepny(pair<int, int> cur, int nowe)
{
	return (max((cur.first * nowe + cur.second - 1), 0) / max(cur.second, 1));
}

int main() 
{
	int n, l;
	cin >> n >> l;
	vector<int> per;
	vector<pair<int, int>> miejsca;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= l; j++)
		{
			cin >> war[i][j];
			potrz[i] += war[i][j];
			war[i][j] *= n;
			pref[i][j] = pref[i][j - 1] + war[i][j];
			//cout << pref[i][j] << " ";
		}
		//cout << endl;
	}
	int pop_calk, curmin, ktory;
	pair<int, int> pop, curminu, temp;
	pop = {0, 0};
	pop_calk = 0;
	for(int i = 1; i < n; i++)
	{
		curmin = INT_MAX;
		for(int j = 1; j <= n; j++)
		{
			if(!czy_juz[j])
			{
				while(gdzie_jestem[j] <= l && pref[j][gdzie_jestem[j]] - pref[j][pop_calk] - nastepny(pop, war[j][gdzie_jestem[j + 1]]) < potrz[j])
				{
					/*if(j == 3)
					{
						cout << gdzie_jestem[j] << endl;
					}*/
					//cout << gdzie_jestem[j] << endl;
					//cout << nastepny(pop, war[j][gdzie_jestem[j + 1]] / n) << endl;
					//cout << pref[j][gdzie_jestem[j]] - pref[j][pop_calk] - nastepny(pop, war[j][gdzie_jestem[j + 1]] / n) << endl;
					gdzie_jestem[j]++;
				}
				if(gdzie_jestem[j] > l)
				{
					/*cout << i << " " << j << endl;
					for(auto x : miejsca)
					{
						cout << x.first << " " << x.second << endl;
					}
					for(auto x : per)
					{
						cout << x << " ";
					}*/
					cout << "-1" << endl;
					return 0;
				}
				temp.first = pref[j][gdzie_jestem[j]] - pref[j][gdzie_jestem[j] - 1] - (pref[j][gdzie_jestem[j]] - pref[j][pop_calk] - nastepny(pop, war[j][gdzie_jestem[j + 1]]) - potrz[j]);
				temp.second = war[j][gdzie_jestem[j]];
				if(gdzie_jestem[j] < curmin)
				{
					curmin = gdzie_jestem[j];
					ktory = j;
					curminu = temp;
				}
				else if(gdzie_jestem[j] == curmin)
				{
					if(curminu.first * temp.second > temp.first * curminu.second)
					{
						curminu = temp;
						ktory = j;
					}
				}
			}
		}
		pop_calk = curmin - 1;
		pop = curminu;
		czy_juz[ktory] = true;
		per.push_back(ktory);
		curminu.first += curminu.second * pop_calk;
		miejsca.push_back(curminu);
		for(int j = 1; j <= n; j++)
		{
			gdzie_jestem[j] = curmin;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(!czy_juz[i])
		{
			per.push_back(i);
		}
	}
	for(auto x : miejsca)
	{
		cout << x.first << " " << x.second << endl;
	}
	for(auto x : per)
	{
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71