oj.uz

Submission #203017

# Submission time Handle Problem Language Result Execution time Memory
203017 2020-02-19T03:26:51 Z arnold518 코알라 (JOI13_koala) C++14
100 / 100
 124 ms 7912 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e18;

int N;
ll S, E, D, A;
ll T[MAXN+10], B[MAXN+10];

ll dp[MAXN+10];

struct BIT
{
	ll tree[MAXN+10];
	vector<ll> comp;
	BIT() { for(int i=0; i<MAXN+10; i++) tree[i]=-INF; }
	void uniq()
	{
		sort(comp.begin(), comp.end());
		comp.erase(unique(comp.begin(), comp.end()), comp.end());
	}
	void update(ll i, ll x) { for(; i<=comp.size(); i+=(i&-i)) tree[i]=max(tree[i], x); }
	ll query(ll i) { ll ret=-INF; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; }

	ll getcomp(ll x)
	{
		return upper_bound(comp.begin(), comp.end(), x)-comp.begin();
	}
	void update2(ll i, ll x) { update(getcomp(i), x); }
	ll query2(ll i) { return query(getcomp(i)); }
}bitl, bitr;

int main()
{
	int i, j;

	scanf("%lld%lld%lld%lld%d", &S, &E, &D, &A, &N);
	for(i=1; i<=N; i++) scanf("%lld%lld", &T[i], &B[i]);
	T[0]=S; T[N+1]=E;
	
	for(i=0; i<=N+1; i++) bitl.comp.push_back(T[i]%D+1);
	for(i=0; i<=N+1; i++) bitr.comp.push_back(D-T[i]%D);

	bitl.uniq();
	bitr.uniq();

	for(i=0; i<=N+1; i++)
	{
		if(i) dp[i]=max(bitl.query2(T[i]%D)-A, bitr.query2(D-T[i]%D))+B[i]-A*(T[i]/D);
		else dp[i]=0;	

		bitl.update2(T[i]%D+1, dp[i]+A*(T[i]/D));
		bitr.update2(D-T[i]%D, dp[i]+A*(T[i]/D));
	}
	printf("%lld\n", dp[N+1]);
}

Compilation message

koala.cpp: In member function 'void BIT::update(ll, ll)':
koala.cpp:27:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  void update(ll i, ll x) { for(; i<=comp.size(); i+=(i&-i)) tree[i]=max(tree[i], x); }
                                  ~^~~~~~~~~~~~~
koala.cpp: In function 'int main()':
koala.cpp:40:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
koala.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%d", &S, &E, &D, &A, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:43:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld%lld", &T[i], &B[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1912 KB Output is correct
2 Correct 7 ms 1912 KB Output is correct
3 Correct 6 ms 1912 KB Output is correct
4 Correct 6 ms 1912 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 6 ms 1912 KB Output is correct
7 Correct 6 ms 1912 KB Output is correct
8 Correct 7 ms 1912 KB Output is correct
9 Correct 6 ms 1912 KB Output is correct
10 Correct 6 ms 1916 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5864 KB Output is correct
2 Correct 63 ms 5868 KB Output is correct
3 Correct 32 ms 4588 KB Output is correct
4 Correct 65 ms 6124 KB Output is correct
5 Correct 38 ms 4336 KB Output is correct
6 Correct 25 ms 3564 KB Output is correct
7 Correct 34 ms 5860 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 5864 KB Output is correct
2 Correct 124 ms 6224 KB Output is correct
3 Correct 107 ms 7912 KB Output is correct
4 Correct 90 ms 7912 KB Output is correct
5 Correct 76 ms 5740 KB Output is correct
6 Correct 59 ms 4848 KB Output is correct