Submission #3909475

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<llll> vllll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define repC3(vari,varj,vark,n)  for(int vari=0;vari<(n)-2;++vari)for(int varj=vari+1;varj<(n)-1;++varj)for(int vark=varj+1;vark<(n);++vark)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

template<class T> inline void amin(T & a, T const & b) { a = min(a, b); }
template<class T> inline void amax(T & a, T const & b) { a = max(a, b); }
template<typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template<typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }



int stat[59][59][59];
bitset<216000> dp;
char maxs[3];
int maxv=-1;

inline int IJK(int i,int j,int k) { return i*3600 + j*60 + k; }

void scan(char* buf) {
    int L = strlen(buf);
    if (buf[L-1] < 32) --L;
    if (buf[L-1] < 32) --L;
    buf[L] = 0;

    dp.reset();

    rep(at,L) {
        int ch = buf[at] - 64;

        for (int i=1; i<59; ++i) {
            if (i==27) i=33;

            for (int j=1; j<59; ++j) {
                if (j==27) j=33;

                if (!dp.test(IJK(i,j,0))) continue;
   
                if (!dp.test(IJK(i,j,ch))) {
                    ++stat[i][j][ch];
                    if (stat[i][j][ch] > maxv
                       || (stat[i][j][ch] == maxv && (
                               i < maxs[0] || (i == maxs[0] && (j < maxs[1] || (j == maxs[1] && ch < maxs[2])))
                               ))) {
                        maxv = stat[i][j][ch];
                        maxs[0]=i; maxs[1]=j; maxs[2]=ch;
                    }
                    dp.set(IJK(i,j,ch), true);
                }
            }
            if (!dp.test(IJK(i,0,0))) continue;
            dp.set(IJK(i,ch,0), true);
        }
        dp.set(IJK(ch,0,0), true);
    }
}


int main() {
    char buf[90010];
    fgets(buf, 256, stdin);
    int N = atoi(buf);

    rep(i,3) maxs[i] = 63;
    maxv = -1;

    mset(stat, 0);
    rep(i,N){
        fgets(buf, 90010, stdin);
        scan(buf);
    }

    rep(i,3) putchar(64 + maxs[i]); putchar('\n');
    return 0;
}

Submission Info

Submission Time
Task D - Three Letters
User naoya_t
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3381 Byte
Status
Exec Time 941 ms
Memory 1152 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:99:27: warning: ignoring return value of ‘char* fgets(char*, int, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
     fgets(buf, 256, stdin);
                           ^
./Main.cpp:107:33: warning: ignoring return value of ‘char* fgets(char*, int, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
         fgets(buf, 90010, stdin);
                                 ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 500 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
01.txt 429 ms 1024 KB
02.txt 710 ms 1152 KB
03.txt 473 ms 1024 KB
04.txt 699 ms 1024 KB
05.txt 941 ms 1024 KB
06.txt 825 ms 1024 KB
07.txt 434 ms 1024 KB
08.txt 832 ms 1024 KB
09.txt 434 ms 1024 KB
10.txt 503 ms 1024 KB
11.txt 429 ms 1024 KB
12.txt 430 ms 1024 KB
13.txt 429 ms 1024 KB
sample_01.txt 2 ms 1024 KB
sample_02.txt 2 ms 1024 KB