oj.uz

Submission #284228

# Submission time Handle Problem Language Result Execution time Memory
284228 2020-08-27T04:30:56 Z 송준혁(#5749) Discharging (NOI20_discharging) C++17
0 / 100
 171 ms 8184 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;

int N;
LL A[1010101];

bool chk(pii a, pii b, pii c){
	return (b.se-a.se)*(b.fi-c.fi) <= (c.se-b.se)*(a.fi-b.fi);
}

struct CHT{
	int p=0;
	vector<pii> CH;
	void push(pii l){
		while (CH.size()>1 && chk(l, CH.back(), CH[CH.size()-2])) CH.pop_back();
		if (p >= CH.size()) p = CH.size()-1;
		CH.pb(l);
	}
	LL f(LL x){
		while (p < CH.size()-1 && CH[p].fi*x+CH[p].se > CH[p+1].fi*x+CH[p+1].se) p++;
		return CH[p].fi*x+CH[p].se;
	}
} D;

int main(){
	scanf("%d", &N);
	for (int i=1; i<=N; i++) scanf("%lld", &A[i]), A[i]=max(A[i], A[i-1]);
	D.push(pii(N, 0));
	for (int i=1; i<N; i++){
		LL r = D.f(A[i]);
		D.push(pii(N-i, r));
	}
	printf("%lld\n", D.f(A[N]));
	return 0;
}

Compilation message

Discharging.cpp: In member function 'void CHT::push(pii)':
Discharging.cpp:21:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if (p >= CH.size()) p = CH.size()-1;
      |       ~~^~~~~~~~~~~~
Discharging.cpp: In member function 'LL CHT::f(LL)':
Discharging.cpp:25:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   while (p < CH.size()-1 && CH[p].fi*x+CH[p].se > CH[p+1].fi*x+CH[p+1].se) p++;
      |          ~~^~~~~~~~~~~~~
Discharging.cpp: In function 'int main()':
Discharging.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Discharging.cpp:32:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  for (int i=1; i<=N; i++) scanf("%lld", &A[i]), A[i]=max(A[i], A[i-1]);
      |                           ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -