oj.uz

답안 #798337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
798337 2023-07-30T15:39:22 Z prvocislo 팀들 (IOI15_teams) C++17
100 / 100
 1216 ms 248508 KB 
#pragma once
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int len = 2e7 + 5;
int sum[len], ls[len], rs[len], l[len], r[len], cnt = 0;
int build(int li, int ri)
{
	int vr = cnt++;
	l[vr] = li, r[vr] = ri, sum[vr] = 0;
	if (li != ri) ls[vr] = build(li, (li + ri) / 2), rs[vr] = build((li + ri) / 2 + 1, ri);
	return vr;
}
int upd(int i, int vr) // vrati novy koren
{
	if (i < l[vr] || i > r[vr]) return vr;
	int v2 = cnt++;
	sum[v2] = sum[vr] + 1;
	l[v2] = l[vr], r[v2] = r[vr];
	if (l[vr] != r[vr]) ls[v2] = upd(i, ls[vr]), rs[v2] = upd(i, rs[vr]);
	return v2;
}
int query(int li, int ri, int vr)
{
	if (ri < l[vr] || li > r[vr]) return 0;
	if (li <= l[vr] && r[vr] <= ri) return sum[vr];
	return query(li, ri, ls[vr]) + query(li, ri, rs[vr]);
}
vector<int> ro;
int n;
void init(int N, int A[], int B[])
//void init(int N, vector<int> A, vector<int> B)
{
	n = N, cnt = 0;
	ro.resize(N + 1);
	vector<vector<int> > e(N + 1);
	for (int i = 0; i < N; i++) e[A[i]].push_back(B[i]);
	ro[0] = build(0, N);
	for (int i = 0; i <= N; i++)
	{
		if (i) ro[i] = ro[i - 1];
		for (int x : e[i]) ro[i] = upd(x, ro[i]);
	}
}
int can(int M, int K[])
//int can(int M, vector<int> K)
{
	int s = 0;
	for (int i = 0; i < M; i++) s += K[i];
	if (s > n) return 0;
	sort(K, K + M);
	//sort(K.begin(), K.end());
	vector<pair<int, int> > v;
	for (int i = 0; i < M; i++)
	{
		if (!i || v.back().first != K[i]) v.push_back({ K[i], 0 });
		v.back().second += K[i];
	}
	vector<int> dp(v.size(), 0); // najvacsie mozne places - kids
	for (int ri = v.size() - 1; ri >= 0; ri--)
	{
		dp[ri] = v[ri].second - (query(v[ri].first, n, ro[v[ri].first]));
		if (dp[ri] > 0) return 0;
		int mx = -1e9;
		for (int li = ri + 1; li < v.size(); li++) if (dp[li] > mx)
		{
			mx = dp[li];
			dp[ri] = max(dp[ri], dp[li] + v[ri].second - query(v[ri].first, v[li].first - 1, ro[v[ri].first]));
			if (dp[ri] > 0) return 0;
		}
	}
	return 1;
}

Compilation message

teams.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:75:25: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |  for (int ri = v.size() - 1; ri >= 0; ri--)
      |                ~~~~~~~~~^~~
teams.cpp:80:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int li = ri + 1; li < v.size(); li++) if (dp[li] > mx)
      |                         ~~~^~~~~~~~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 312 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 312 KB Output is correct
26 Correct 0 ms 340 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 45220 KB Output is correct
2 Correct 91 ms 45232 KB Output is correct
3 Correct 91 ms 45284 KB Output is correct
4 Correct 84 ms 45412 KB Output is correct
5 Correct 32 ms 43856 KB Output is correct
6 Correct 31 ms 43868 KB Output is correct
7 Correct 31 ms 43800 KB Output is correct
8 Correct 31 ms 43836 KB Output is correct
9 Correct 37 ms 42392 KB Output is correct
10 Correct 30 ms 44040 KB Output is correct
11 Correct 30 ms 44092 KB Output is correct
12 Correct 32 ms 44204 KB Output is correct
13 Correct 38 ms 44492 KB Output is correct
14 Correct 48 ms 43480 KB Output is correct
15 Correct 72 ms 45108 KB Output is correct
16 Correct 72 ms 45136 KB Output is correct
17 Correct 35 ms 44492 KB Output is correct
18 Correct 35 ms 44644 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 45568 KB Output is correct
2 Correct 96 ms 45568 KB Output is correct
3 Correct 217 ms 45564 KB Output is correct
4 Correct 87 ms 45440 KB Output is correct
5 Correct 69 ms 43972 KB Output is correct
6 Correct 54 ms 44044 KB Output is correct
7 Correct 69 ms 43980 KB Output is correct
8 Correct 57 ms 44072 KB Output is correct
9 Correct 31 ms 42328 KB Output is correct
10 Correct 34 ms 44072 KB Output is correct
11 Correct 37 ms 44200 KB Output is correct
12 Correct 67 ms 44284 KB Output is correct
13 Correct 126 ms 44688 KB Output is correct
14 Correct 207 ms 44932 KB Output is correct
15 Correct 98 ms 45264 KB Output is correct
16 Correct 96 ms 45312 KB Output is correct
17 Correct 60 ms 44668 KB Output is correct
18 Correct 58 ms 44744 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 797 ms 248420 KB Output is correct
2 Correct 800 ms 248372 KB Output is correct
3 Correct 1216 ms 248508 KB Output is correct
4 Correct 804 ms 248372 KB Output is correct
5 Correct 286 ms 240008 KB Output is correct
6 Correct 223 ms 239816 KB Output is correct
7 Correct 272 ms 239784 KB Output is correct
8 Correct 267 ms 239932 KB Output is correct
9 Correct 158 ms 230004 KB Output is correct
10 Correct 160 ms 237876 KB Output is correct
11 Correct 192 ms 238508 KB Output is correct
12 Correct 277 ms 239048 KB Output is correct
13 Correct 604 ms 241908 KB Output is correct
14 Correct 1139 ms 245784 KB Output is correct
15 Correct 584 ms 246824 KB Output is correct
16 Correct 621 ms 246860 KB Output is correct
17 Correct 224 ms 241516 KB Output is correct
18 Correct 226 ms 241588 KB Output is correct