Submission #592475

#TimeUsernameProblemLanguageResultExecution timeMemory
592475AA_SurelyTeam Contest (JOI22_team)C++17
35 / 100
1293 ms16212 KiB
#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(LL i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(LL i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 2e5 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

LL n;
LL a[N], b[N], c[N];
VPLL g[3][310];

void init() {
    cin >> n;
    F0R(i, n) cin >> a[i] >> b[i] >> c[i];
    return;
}

int main() {
    IOS;
    init();

    LL sum = -1;
    if(n <= 300) {
        F0R(j, n) F0R(i, n) F0R(k, n) {
            if(a[j] > max(a[i], a[k]) && b[i] > max(b[j], b[k]) && c[k] > max(c[j], c[i])) {
                sum = max(sum, a[j] + b[i] + c[k]);
            }
        }

        cout << sum;
        return 0;
    } 
    
    else {
        F0R(i, n) {
            g[0][a[i]].pb({b[i], c[i]});
            g[1][b[i]].pb({a[i], c[i]});
            g[2][c[i]].pb({a[i], b[i]});
        }

        F0R(j, 3) {
            F0R(x, 301) {
                sort(ALL(g[j][x]));
                FOR(i, 1, g[j][x].size())
                    g[j][x][i].S = min(g[j][x][i].S, g[j][x][i - 1].S);

                g[j][x].resize(unique(ALL(g[j][x])) - g[j][x].begin());							
            }			
        }

        FOR(i, 1, 301) {
            FOR(j, 1, 301) {
                FOR(k, 1, 301) {
                    LL l = 0, r = ((LL)g[0][i].size()) - 1, ans = -1, ans2 = -1, ans3 = -1;

                    while(l <= r) {
                        LL m = (l + r) >> 1;
                        if(g[0][i][m].F < j) {
                            ans = m;
                            l = m + 1;
                        } 
                        
                        else r = m - 1;
                    }

                    if(ans == -1) continue;
                    l = 0, r = ((LL)g[1][j].size()) - 1;

                    while(l <= r) {
                        LL m = (l + r) >> 1;
                        if(g[1][j][m].F < i) {
                            ans2 = m;
                            l = m + 1;
                        } 
                        
                        else r = m - 1;
                    }

                    if(ans2 == -1) continue;
                    l = 0, r = ((LL)g[2][k].size()) - 1;
                    while(l <= r) {
                        LL m = (l + r) >> 1;

                        if(g[2][k][m].F < i) {
                            ans3 = m;
                            l = m + 1;
                        } 
                        else r = m - 1;
                    }

                    if(ans3 == -1) continue;

                    if(g[0][i][ans].S < k && g[1][j][ans2].S < k && g[2][k][ans3].S < j) {

                        sum = max(sum, i + j + k);
                    }
                }
            }
        }

        cout << sum;
    }
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:3:34: warning: comparison of integer expressions of different signedness: 'LL' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i,x,n)  for(LL i=x; i<n; i++)
......
   71 |                 FOR(i, 1, g[j][x].size())
      |                     ~~~~~~~~~~~~~~~~~~~~
team.cpp:71:17: note: in expansion of macro 'FOR'
   71 |                 FOR(i, 1, g[j][x].size())
      |                 ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...