oj.uz

Submission #493134

# Submission time Handle Problem Language Result Execution time Memory
493134 2021-12-10T06:30:04 Z freddy645645 Semiexpress (JOI17_semiexpress) C++17
100 / 100
 15 ms 5028 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

//#define double long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
#define pb push_back
#define UNIQUE(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin());
#define ALL(X) X.begin(),X.end()
#define F(i,n)  FF(i,0,(n))
#define F1(i,n)  FF(i,1,(n)+1)
#define FF(i,n,m) for(int i=(int)n;i<int(m);++i)
#define rF(i,a,b) for(int i=a;i>=(int)b;--i)
#define mkp(a,b) make_pair(a,b)
#define Fi first
#define Se second
#define int ll
//#pragma GCC optimize("O3")//,unroll-loops
//#pragma GCC target("popcnt")

using namespace std;

template<typename T> bool remax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool remin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> void clear(T& a){
	T b;
	swap(a,b);
	return;
}
using ll=long long;
using ull=unsigned long long;
using int128= __int128_t;
using uint128= __uint128_t;
using pii =pair<int,int> ;
const double pi=acos(-1);
const int N=2E5+5;
const ll M=105;
const ll INF_64=0x3f3f3f3f3f3f3f3f;
const int INF_32=0x3f3f3f3f;
const int16_t INF_16=0x3f3f;
const int klog=20;
const int mod=1000000007;//1000000007;//998244353
const double eps=1E-3;
void gen(){
}

void sol(){
    int n,m,k;cin>>n>>m>>k;
    int a,b,c;cin>>a>>b>>c;
    int t;cin>>t;
    vector<int> S(m);
    F(i,m) cin>>S[i];
    k-=m;
    vector<int> choose;
    int an=0;
    F(i,m-1){
    	int cur=(S[i]-1)*b;
    	int p=S[i];
    	vector<int> tmp;
    	while(cur<=t&&p<S[i+1]&&tmp.size()<(k+1)){
    		int nxt=min((t-cur)/a,S[i+1]-p-1);
    		tmp.pb(nxt+1);
    		cur+=(nxt+1)*c;
    		p+=nxt+1;
		}
		if(tmp.size()){
			an+=tmp[0];
			choose.insert(choose.end(),tmp.begin()+1,tmp.end());
		}
	}
	sort(ALL(choose),greater<int>());
	if((S[m-1]-1)*b<=t)++an;
	F(i,min<int>(k,choose.size()))
		an+=choose[i];
	--an;
	cout<<an<<"\n";
}

int32_t main(){
    #ifdef LOCAL
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    #endif // LOCAL
    IOS;
    int t=1;
    gen();
    //cin>>t;
    FF(i,1,t+1){
        //cout<<"Case #"<<i<<": ";
        sol();
    }
}

Compilation message

semiexpress.cpp: In function 'void sol()':
semiexpress.cpp:59:40: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   59 |      while(cur<=t&&p<S[i+1]&&tmp.size()<(k+1)){
      |                              ~~~~~~~~~~^~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 0 ms 336 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 15 ms 5028 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 9 ms 2736 KB Output is correct
30 Correct 6 ms 2312 KB Output is correct