oj.uz

Submission #203686

# Submission time Handle Problem Language Result Execution time Memory
203686 2020-02-21T20:15:03 Z blacktulip Semiexpress (JOI17_semiexpress) C++17
100 / 100
 72 ms 14440 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
typedef pair< lo,PII > PIII;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define int long long
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 100000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 3005;
const lo mod = 1000000007;
 
int n,m,b,c,a,k,flag,t,PS[li][li];
int cev,ans;
map<int,int> vis;
string s;
set<int> st;
set<PIII> st1;
vector<int> v,vec[li];

inline int solve(){
	int cevap=0;
	for(int i=1;i<m;i++){
		st1.insert(mp(-vec[i][1]+vec[i][0],mp(i,1)));
		//~ cout<<vec[i][1]<<endl;
		cevap+=vec[i][0];
	}
	//~ int cevap=0;
	while(k){
		k--;
		auto it=st1.begin();
		PIII p=*it;
		cevap-=p.fi;
		//~ cout<<p.fi<<endl;
		if(p.se.se+1<vec[p.se.fi].size())
		//~ cout<<(vec[p.se.fi][p.se.se+1]-vec[p.se.fi][p.se.se])<<"YESYES\n";
		st1.insert(mp(-(vec[p.se.fi][p.se.se+1]-vec[p.se.fi][p.se.se]),mp(p.se.fi,p.se.se+1)));
		st1.erase(it);
	}
	if((n-1)*b>t)cevap--;
	return cevap;
}

main(void){
	//~ memset(dp,-1,sizeof(dp));
	scanf("%lld %lld %lld",&n,&m,&k);
	scanf("%lld %lld %lld",&a,&b,&c);
	scanf("%lld",&t);
	for(int i=1;i<=m;i++){
		int x;
		scanf("%lld",&x);
		vis[x]=i;
		v.pb(x);
		st.insert(x);
		k--;
	}
	int last=1;
	for(int i=1;i<m;i++){
		last=v[i-1]-1;
		for(int j=0;j<=k;j++){
			int bas=last+1;
			int son=v[i]-1;
			while(bas<=son){
				//~ cout<<ort<<" : ; "<<(v[i-1]-1)*b+(last+1-v[i-1])*c+(ort-last-1)*a<<endl;
				if((v[i-1]-1)*b+(last+1-v[i-1])*c+(ort-last-1)*a>t)son=ort-1;
				else bas=ort+1;
			}
			vec[i].pb(son-v[i-1]+1);
			//~ cout<<"()()"<<son<<"()"<<son-v[i-1]+1<<"()()"<<endl;
			last=son;
		}
	}
	printf("%lld\n",solve());
	return 0;
}

Compilation message

semiexpress.cpp: In function 'long long int solve()':
semiexpress.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p.se.se+1<vec[p.se.fi].size())
      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
semiexpress.cpp: At global scope:
semiexpress.cpp:58:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
semiexpress.cpp: In function 'int main()':
semiexpress.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&a,&b,&c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&t);
  ~~~~~^~~~~~~~~~~
semiexpress.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&x);
   ~~~~~^~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 504 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 504 KB Output is correct
19 Correct 36 ms 6648 KB Output is correct
20 Correct 72 ms 11896 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 16 ms 2296 KB Output is correct
23 Correct 60 ms 14440 KB Output is correct
24 Correct 7 ms 760 KB Output is correct
25 Correct 5 ms 632 KB Output is correct
26 Correct 6 ms 760 KB Output is correct
27 Correct 6 ms 760 KB Output is correct
28 Correct 6 ms 760 KB Output is correct
29 Correct 25 ms 4472 KB Output is correct
30 Correct 17 ms 2040 KB Output is correct