oj.uz

Submission #141724

# Submission time Handle Problem Language Result Execution time Memory
141724 2019-08-09T01:00:16 Z imsifile Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 65264 KB 
    #include "squad.h"
    #include <algorithm>
    #include <stdio.h>
    using namespace std;
     
    typedef long long lld;
     
    struct coord {
    	lld x, y; int ix;
    	bool operator< (const coord& c) const {
    		if(x!=c.x) return x<c.x;
    		return y<c.y;
    	}
    } AP[1001001], DP[1001001];
     
    int N;
     
    lld ccw(coord a, coord b, coord c){ // clockwise < 0
    	return (a.x*b.y+b.x*c.y+c.x*a.y) - (a.y*b.x+b.y*c.x+c.y*a.x);
    }
     
    void makehull(coord *ba, vector<int> &chk, int val, vector<coord> &cvx){
    	cvx.clear();
    	for(int i=0; i<N; i++){
    		int sz;
    		if(chk[ba[i].ix]==val) continue;
    		while(1){
    			sz=cvx.size();
    			if(sz<2) break;
    			if(ccw(cvx[sz-2], cvx[sz-1], ba[i]) < 0) break;
    			cvx.pop_back();
    		}
    		cvx.push_back(ba[i]);
    	}
    }
     
    void threehull(coord *ba, vector<coord> &cvx, vector<coord> &odd, vector<coord> &even){
    	vector<int> chk(N,0);
    	sort(ba, ba+N);
    	makehull(ba, chk, 1, cvx);
    	for(int i=cvx.size(); i--;){
    		if(i%2) chk[cvx[i].ix]=1;
    		else chk[cvx[i].ix]=2;
    	}
    	makehull(ba, chk, 1, odd);
    	makehull(ba, chk, 2, even);
    }
     
    vector<coord> Acv, Aov, Aev, Dcv, Dov, Dev;
     
    void Init(int N_, vector<int> A, vector<int> D, vector<int> P){
    	N=N_;
    	for(int i=0; i<N; i++){
    		AP[i].ix=i, AP[i].x=A[i], AP[i].y=P[i];
    		DP[i].ix=i, DP[i].x=D[i], DP[i].y=P[i];
    	}
    	threehull(AP, Acv, Aov, Aev);
    	threehull(DP, Dcv, Dov, Dev);
    }
     
    int getfirst(lld A, lld B, vector<coord> cvx){
    	int mx=0;
    	for(int i=cvx.size(); --i;){
    		if(cvx[mx].x*A + cvx[mx].y*B < cvx[i].x*A + cvx[i].y*B) mx=i;
    	}
    	return mx;
    }
     
    coord A1, A2, D1, D2;
     
    lld BestSquad(int X, int Y){
    	int ix;
    	ix=getfirst(X, Y, Acv), A1=Acv[ix];
    	if(ix%2) ix=getfirst(X, Y, Aov), A2=Aov[ix];
    	else ix=getfirst(X, Y, Aev), A2=Aev[ix];
     
    	ix=getfirst(X, Y, Dcv), D1=Dcv[ix];
    	if(ix%2) ix=getfirst(X, Y, Dov), D2=Dov[ix];
    	else ix=getfirst(X, Y, Dev), D2=Dev[ix];
     
    	if(A1.ix != D1.ix) return (A1.x+D1.x)*X + (A1.y+D1.y)*Y;
    	return max((A2.x+D1.x)*X + (A2.y+D1.y)*Y, (A1.x+D2.x)*X + (A1.y+D2.y)*Y);
    }

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 286 ms 22800 KB Output is correct
4 Correct 286 ms 22648 KB Output is correct
5 Correct 20 ms 4208 KB Output is correct
6 Correct 336 ms 65264 KB Output is correct
7 Correct 334 ms 65140 KB Output is correct
8 Correct 331 ms 65016 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 568 ms 25080 KB Output is correct
4 Correct 560 ms 25076 KB Output is correct
5 Correct 1990 ms 2524 KB Output is correct
6 Execution timed out 3030 ms 45368 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 286 ms 22800 KB Output is correct
4 Correct 286 ms 22648 KB Output is correct
5 Correct 20 ms 4208 KB Output is correct
6 Correct 336 ms 65264 KB Output is correct
7 Correct 334 ms 65140 KB Output is correct
8 Correct 331 ms 65016 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 568 ms 25080 KB Output is correct
12 Correct 560 ms 25076 KB Output is correct
13 Correct 1990 ms 2524 KB Output is correct
14 Execution timed out 3030 ms 45368 KB Time limit exceeded
15 Halted 0 ms 0 KB -