oj.uz

Submission #976629

# Submission time Handle Problem Language Result Execution time Memory
976629 2024-05-06T23:03:59 Z leanchec Aliens (IOI16_aliens) C++17
0 / 100
 5 ms 20948 KB 
#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[110][50100];
vector<pair<int,int>> aux;

ll sq(ll a){return a*a;}

void solve(int qtd,int l, int r, int p, int q){
	int mid=(l+r)>>1, opt=-1;
	for(int i=p; i<=min(q, mid-1); i++){
		if(dp[qtd][mid]>dp[qtd-1][i]+sq(aux[mid].second-aux[i+1].first+1)-max((ll)0, sq(aux[i].second-aux[i+1].first+1))){
			dp[qtd][mid]=dp[qtd-1][i]+sq(aux[mid].second-aux[i+1].first+1)-max((ll)0, sq(aux[i].second-aux[i+1].first+1));
			opt=i;
		}
	}
	if(l<mid)solve(qtd, l, mid-1, p, opt);
	if(mid<r)solve(qtd, mid+1, r, opt, q);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	aux.clear();
	for(int i=0; i<n; i++){
		aux.push_back({min(r[i], c[i]), -max(r[i], c[i])});
	}

	sort(aux.begin(), aux.end());

	vector<pair<int,int>> temp;
	temp.push_back({-1, -1});
	for(auto cur:aux){
		if(-cur.second>temp.back().second)temp.push_back({cur.first, -cur.second});
	}
	aux=temp;

	for(int i=1; i<=k; i++){
		for(int j=1; j<=aux.size(); j++){
			dp[i][j]=1e18;
		}
	}

	for(int i=1; i<aux.size(); i++)
		dp[1][i]=sq(aux[i].second-aux[i].first+1);

	for(int i=2; i<=min((int)aux.size()-1, k); i++)
		solve(i, 1, aux.size()-1, 1, aux.size()-1);

    return dp[min((int)aux.size()-1, k)][aux.size()-1];
}

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j=1; j<=aux.size(); j++){
      |                ~^~~~~~~~~~~~
aliens.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=1; i<aux.size(); i++)
      |               ~^~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Correct answer: answer = 4
2 Correct 1 ms 2396 KB Correct answer: answer = 4
3 Correct 1 ms 2396 KB Correct answer: answer = 4
4 Correct 1 ms 2396 KB Correct answer: answer = 12
5 Correct 1 ms 2496 KB Correct answer: answer = 52
6 Correct 2 ms 4440 KB Correct answer: answer = 210
7 Correct 1 ms 4536 KB Correct answer: answer = 88
8 Correct 1 ms 4444 KB Correct answer: answer = 7696
9 Correct 5 ms 20948 KB Correct answer: answer = 1
10 Correct 3 ms 20824 KB Correct answer: answer = 2374
11 Correct 3 ms 20828 KB Correct answer: answer = 9502
12 Correct 2 ms 20828 KB Correct answer: answer = 49
13 Correct 3 ms 20828 KB Correct answer: answer = 151
14 Correct 2 ms 20828 KB Correct answer: answer = 7550
15 Correct 3 ms 20828 KB Correct answer: answer = 7220
16 Correct 3 ms 20828 KB Correct answer: answer = 7550
17 Correct 3 ms 20828 KB Correct answer: answer = 10000
18 Correct 3 ms 20932 KB Correct answer: answer = 10000
19 Incorrect 3 ms 20828 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Correct answer: answer = 1
2 Incorrect 1 ms 2392 KB Wrong answer: output = 1, expected = 4
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Correct answer: answer = 4
2 Correct 1 ms 2396 KB Correct answer: answer = 4
3 Correct 1 ms 2396 KB Correct answer: answer = 4
4 Correct 1 ms 2396 KB Correct answer: answer = 12
5 Correct 1 ms 2496 KB Correct answer: answer = 52
6 Correct 2 ms 4440 KB Correct answer: answer = 210
7 Correct 1 ms 4536 KB Correct answer: answer = 88
8 Correct 1 ms 4444 KB Correct answer: answer = 7696
9 Correct 5 ms 20948 KB Correct answer: answer = 1
10 Correct 3 ms 20824 KB Correct answer: answer = 2374
11 Correct 3 ms 20828 KB Correct answer: answer = 9502
12 Correct 2 ms 20828 KB Correct answer: answer = 49
13 Correct 3 ms 20828 KB Correct answer: answer = 151
14 Correct 2 ms 20828 KB Correct answer: answer = 7550
15 Correct 3 ms 20828 KB Correct answer: answer = 7220
16 Correct 3 ms 20828 KB Correct answer: answer = 7550
17 Correct 3 ms 20828 KB Correct answer: answer = 10000
18 Correct 3 ms 20932 KB Correct answer: answer = 10000
19 Incorrect 3 ms 20828 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Correct answer: answer = 4
2 Correct 1 ms 2396 KB Correct answer: answer = 4
3 Correct 1 ms 2396 KB Correct answer: answer = 4
4 Correct 1 ms 2396 KB Correct answer: answer = 12
5 Correct 1 ms 2496 KB Correct answer: answer = 52
6 Correct 2 ms 4440 KB Correct answer: answer = 210
7 Correct 1 ms 4536 KB Correct answer: answer = 88
8 Correct 1 ms 4444 KB Correct answer: answer = 7696
9 Correct 5 ms 20948 KB Correct answer: answer = 1
10 Correct 3 ms 20824 KB Correct answer: answer = 2374
11 Correct 3 ms 20828 KB Correct answer: answer = 9502
12 Correct 2 ms 20828 KB Correct answer: answer = 49
13 Correct 3 ms 20828 KB Correct answer: answer = 151
14 Correct 2 ms 20828 KB Correct answer: answer = 7550
15 Correct 3 ms 20828 KB Correct answer: answer = 7220
16 Correct 3 ms 20828 KB Correct answer: answer = 7550
17 Correct 3 ms 20828 KB Correct answer: answer = 10000
18 Correct 3 ms 20932 KB Correct answer: answer = 10000
19 Incorrect 3 ms 20828 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Correct answer: answer = 4
2 Correct 1 ms 2396 KB Correct answer: answer = 4
3 Correct 1 ms 2396 KB Correct answer: answer = 4
4 Correct 1 ms 2396 KB Correct answer: answer = 12
5 Correct 1 ms 2496 KB Correct answer: answer = 52
6 Correct 2 ms 4440 KB Correct answer: answer = 210
7 Correct 1 ms 4536 KB Correct answer: answer = 88
8 Correct 1 ms 4444 KB Correct answer: answer = 7696
9 Correct 5 ms 20948 KB Correct answer: answer = 1
10 Correct 3 ms 20824 KB Correct answer: answer = 2374
11 Correct 3 ms 20828 KB Correct answer: answer = 9502
12 Correct 2 ms 20828 KB Correct answer: answer = 49
13 Correct 3 ms 20828 KB Correct answer: answer = 151
14 Correct 2 ms 20828 KB Correct answer: answer = 7550
15 Correct 3 ms 20828 KB Correct answer: answer = 7220
16 Correct 3 ms 20828 KB Correct answer: answer = 7550
17 Correct 3 ms 20828 KB Correct answer: answer = 10000
18 Correct 3 ms 20932 KB Correct answer: answer = 10000
19 Incorrect 3 ms 20828 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Correct answer: answer = 4
2 Correct 1 ms 2396 KB Correct answer: answer = 4
3 Correct 1 ms 2396 KB Correct answer: answer = 4
4 Correct 1 ms 2396 KB Correct answer: answer = 12
5 Correct 1 ms 2496 KB Correct answer: answer = 52
6 Correct 2 ms 4440 KB Correct answer: answer = 210
7 Correct 1 ms 4536 KB Correct answer: answer = 88
8 Correct 1 ms 4444 KB Correct answer: answer = 7696
9 Correct 5 ms 20948 KB Correct answer: answer = 1
10 Correct 3 ms 20824 KB Correct answer: answer = 2374
11 Correct 3 ms 20828 KB Correct answer: answer = 9502
12 Correct 2 ms 20828 KB Correct answer: answer = 49
13 Correct 3 ms 20828 KB Correct answer: answer = 151
14 Correct 2 ms 20828 KB Correct answer: answer = 7550
15 Correct 3 ms 20828 KB Correct answer: answer = 7220
16 Correct 3 ms 20828 KB Correct answer: answer = 7550
17 Correct 3 ms 20828 KB Correct answer: answer = 10000
18 Correct 3 ms 20932 KB Correct answer: answer = 10000
19 Incorrect 3 ms 20828 KB Wrong answer: output = 559, expected = 624
20 Halted 0 ms 0 KB -