oj.uz

Submission #51855

# Submission time Handle Problem Language Result Execution time Memory
51855 2018-06-22T04:17:01 Z zetapi Aliens (IOI16_aliens) C++14
0 / 100
 3 ms 548 KB 
#include "aliens.h"
#include "bits/stdc++.h"
using namespace std;

#define pb  push_back
#define mp  make_pair
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e5;
const long long INF=1e12;

vector<pii> vec,lol;

bool cmp(pii X,pii Y)
{
	return X.second<Y.second;
}

long long cost(int X,int Y)
{
	long long side=max(vec[X-1].second,vec[Y-1].second);
	side=max(side,(long long)vec[Y-1].first-vec[X-1].first+1);
	return side*side;
}

long long take_photos(int n=2, int m=6, int k=2, std::vector<int> r={1,4}, std::vector<int> c={4,1}) 
{
	long long N=n,M=m,K=k,dp[n+99][k+99];
	for(int A=0;A<n;A++)
		lol.pb(mp(r[A],abs(r[A]-c[A])+1));
	sort(lol.begin(),lol.end());
	for(int A=0;A<lol.size();A++)
	{
		if(A+1<lol.size() and lol[A].first==lol[A+1].first)
			continue;
		vec.pb((lol[A]));
	}
	for(int A=0;A<=N;A++)
		for(int B=0;B<=K;B++)
			dp[A][B]=INF;
	dp[0][0]=0;
	for(int A=1;A<=vec.size();A++)
	{
		for(int B=0;B<A;B++)
			for(int C=1;C<=K;C++)
				dp[A][C]=min(dp[A][C],dp[B][C-1]+cost(B+1,A));
	}
	long long res=INF;
	for(int A=1;A<=N;A++)
		for(int B=1;B<=K;B++)
			res=min(res,dp[A][B]);
    return res;
}

/*int main()
{
	ios_base::sync_with_stdio(false);
	cout<<take_photos();
	return 0;
}*/

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<lol.size();A++)
              ~^~~~~~~~~~~
aliens.cpp:36:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(A+1<lol.size() and lol[A].first==lol[A+1].first)
      ~~~^~~~~~~~~~~
aliens.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=1;A<=vec.size();A++)
              ~^~~~~~~~~~~~
aliens.cpp:30:16: warning: unused variable 'M' [-Wunused-variable]
  long long N=n,M=m,K=k,dp[n+99][k+99];
                ^

Subtask #1
0 / 4.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 488 KB Correct answer: answer = 1
2 Incorrect 2 ms 548 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 3 ms 376 KB Correct answer: answer = 4
2 Incorrect 3 ms 488 KB Wrong answer: output = 1, expected = 4
3 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 40.0

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