Submission #203686

#	Time	Username	Problem	Language	Result	Execution time	Memory
203686		blacktulip	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	72 ms	14440 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52