oj.uz

Submission #535020

# Submission time Handle Problem Language Result Execution time Memory
535020 2022-03-09T10:08:46 Z nathanlee726 Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 210 ms 8256 KB 
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;

//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif

int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod;
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

int n,k;
pii pt[505],pt2[505];
vector<pii>pt1;
double dp[505][505],tdp[505][505],rd[505][505],rm[505][505];

bool cmp(pii a,pii b){
    if(a.Y==-1&&b.Y==-1){
        return a.X<b.X;
    }
    if(a.Y==-1){
        return false;
    }
    if(b.Y==-1)return true;
    return a.Y<b.Y;
}

signed main(){
	IOS();
	cin>>n>>k;
	F(n)cin>>pt[i].X>>pt[i].Y;
	sort(pt,pt+n,cmp);
	F(n+1)Fi(j,n+1)dp[i][j]=tdp[i][j]=rd[i][j]=-1;
	bug(dp[0][0]);
	dp[0][0]=0;
	Fi(l,k){
        for(int i=0;i<n;i++){
            for(int j=0;j<=l;j++){
                if(dp[i][j]==-1)continue;
                if(pt[i].Y!=-1){
                    if(dp[i+1][j+1]!=-1)dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+(((double)(pt[i].Y))/((double)(j+1))));
                    else dp[i+1][j+1]=dp[i][j]+(((double)(pt[i].Y))/((double)(j+1)));
                }
                if(dp[i+1][j]!=-1)dp[i+1][j]=min(dp[i+1][j],dp[i][j]+(((double)(pt[i].X))/((double)(l+1))));
                else dp[i+1][j]=dp[i][j]+(((double)(pt[i].X))/((double)(l+1)));
            }
        }
        for(int i=0;i<=n;i++)rm[l][i]=dp[i][l];
	}
	rd[n][0]=0;
	for(int i=n-1;i>=0;i--){
        for(int j=0;j<n;j++){
            if(rd[i+1][j]==-1)continue;
            rd[i][j]=(rd[i][j]==-1?rd[i+1][j]:min(rd[i+1][j],rd[i][j]));
            rd[i][j+1]=(rd[i][j+1]==-1?rd[i+1][j]+pt[i].X:min(rd[i][j+1],rd[i+1][j]+pt[i].X));
        }
	}
	double ans=1e18;
	F(k){
        for(int j=i;j<k;j++){
            if(rm[i][j]!=-1)ans=min(ans,rm[i][j]+((double)(rd[j][k-j]))/((double)(i+1)));
            bug(i,j,rm[i][j]);
        }
	}
	cout<<fixed<<setprecision(10);
	cout<<ans<<endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 4 ms 6476 KB Output is correct
6 Correct 7 ms 6732 KB Output is correct
7 Correct 20 ms 7160 KB Output is correct
8 Correct 34 ms 7748 KB Output is correct
9 Correct 55 ms 8176 KB Output is correct
10 Correct 32 ms 7628 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 4 ms 6476 KB Output is correct
6 Correct 7 ms 6732 KB Output is correct
7 Correct 20 ms 7160 KB Output is correct
8 Correct 34 ms 7748 KB Output is correct
9 Correct 55 ms 8176 KB Output is correct
10 Correct 32 ms 7628 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 29 ms 6840 KB Output is correct
13 Correct 22 ms 6848 KB Output is correct
14 Correct 16 ms 6828 KB Output is correct
15 Correct 106 ms 7648 KB Output is correct
16 Correct 86 ms 7560 KB Output is correct
17 Correct 52 ms 7620 KB Output is correct
18 Correct 197 ms 8140 KB Output is correct
19 Correct 160 ms 8244 KB Output is correct
20 Correct 83 ms 8172 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 452 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 452 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 452 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 8220 KB Output is correct
2 Correct 200 ms 8236 KB Output is correct
3 Correct 210 ms 8196 KB Output is correct
4 Incorrect 203 ms 8256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 4 ms 6476 KB Output is correct
6 Correct 7 ms 6732 KB Output is correct
7 Correct 20 ms 7160 KB Output is correct
8 Correct 34 ms 7748 KB Output is correct
9 Correct 55 ms 8176 KB Output is correct
10 Correct 32 ms 7628 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 29 ms 6840 KB Output is correct
13 Correct 22 ms 6848 KB Output is correct
14 Correct 16 ms 6828 KB Output is correct
15 Correct 106 ms 7648 KB Output is correct
16 Correct 86 ms 7560 KB Output is correct
17 Correct 52 ms 7620 KB Output is correct
18 Correct 197 ms 8140 KB Output is correct
19 Correct 160 ms 8244 KB Output is correct
20 Correct 83 ms 8172 KB Output is correct
21 Correct 1 ms 380 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 304 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 0 ms 460 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Incorrect 1 ms 452 KB Output isn't correct
32 Halted 0 ms 0 KB -