Submission #868372


Source Code Expand

Copy
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

const int N=110;

struct P {
    int x1,y1,x2,y2,v;
};

bool operator <( const P &a, const P &b ) {
    return tie(a.x1,a.y1,a.x2,a.y2,a.v)<tie(b.x1,b.y1,b.x2,b.y2,b.v);
}

int n,m,ss[N][N];
char s[N][N];

int get( int x1, int y1, int x2, int y2 ) {
    return ss[x2][y2]-ss[x1-1][y2]-ss[x2][y1-1]+ss[x1-1][y1-1];
}

int main() {
    R(n,m);
    REP1(i,1,n) REP1(j,1,m) R(s[i][j]);
    REP1(i,1,n) REP1(j,1,m) ss[i][j]=ss[i-1][j]+ss[i][j-1]-ss[i-1][j-1]+(s[i][j]=='o');
    int ex=-1,ey=-1;
    REP1(i,1,n) REP1(j,1,m) if ( s[i][j]=='E' ) tie(ex,ey)=tie(i,j);
    assert(ex!=-1);
    vector<P> v,nv;
    v.PB(P{ex,ey,ex,ey,0});
    int ans=0;
    while ( !v.empty() ) {
        nv.clear();
        sort(ALL(v));
        for ( auto &p:v ) {
            ans=max(ans,p.v);
            int x1,y1,x2,y2;
            tie(x1,y1,x2,y2)=tie(p.x1,p.y1,p.x2,p.y2);
            int xx1=x2-ex+1;
            int yy1=y2-ey+1;
            int xx2=x1+(n-ex);
            int yy2=y1+(m-ey);
            int xxx1=max(x1,xx1);
            int yyy1=max(y1,yy1);
            int xxx2=min(x2,xx2);
            int yyy2=min(y2,yy2);
            dump(x1,y1,x2,y2,xx1,yy1,xx2,yy2,p.v);
            if ( x1-1>=xx1 ) nv.PB(P{x1-1,y1,x2,y2,p.v+get(x1-1,yyy1,x1-1,yyy2)});
            if ( y1-1>=yy1 ) nv.PB(P{x1,y1-1,x2,y2,p.v+get(xxx1,y1-1,xxx2,y1-1)});
            if ( x2+1<=xx2 ) nv.PB(P{x1,y1,x2+1,y2,p.v+get(x2+1,yyy1,x2+1,yyy2)});
            if ( y2+1<=yy2 ) nv.PB(P{x1,y1,x2,y2+1,p.v+get(xxx1,y2+1,xxx2,y2+1)});
        }
        v.swap(nv);
    }
    W(ans);
    return 0;
}

Submission Info

Submission Time
Task E - Salvage Robots
User shik
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4452 Byte
Status
Exec Time 2182 ms
Memory 404808 KB

Compile Error

./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                              ^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( int &x ) { scanf("%d",&x); }
                                   ^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                               ^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0 / 1400 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt
Case Name Status Exec Time Memory
0_00.txt 4 ms 256 KB
0_01.txt 4 ms 256 KB
0_02.txt 4 ms 256 KB
0_03.txt 5 ms 384 KB
1_00.txt 4 ms 256 KB
1_01.txt 4 ms 256 KB
1_02.txt 4 ms 256 KB
1_03.txt 4 ms 256 KB
1_04.txt 2117 ms 164284 KB
1_05.txt 2120 ms 164284 KB
1_06.txt 2123 ms 190008 KB
1_07.txt 2121 ms 169144 KB
1_08.txt 2135 ms 325832 KB
1_09.txt 2128 ms 392648 KB
1_10.txt 2142 ms 399688 KB
1_11.txt 2131 ms 326344 KB
1_12.txt 2131 ms 279496 KB
1_13.txt 2117 ms 212816 KB
1_14.txt 2136 ms 339784 KB
1_15.txt 2117 ms 214716 KB
1_16.txt 2136 ms 329416 KB
1_17.txt 2117 ms 212816 KB
1_18.txt 2117 ms 212816 KB
1_19.txt 2131 ms 279624 KB
1_20.txt 2131 ms 278472 KB
1_21.txt 2136 ms 333896 KB
1_22.txt 2132 ms 298184 KB
1_23.txt 2133 ms 300488 KB
1_24.txt 2122 ms 185284 KB
1_25.txt 2122 ms 185068 KB
1_26.txt 2116 ms 163824 KB
1_27.txt 2120 ms 164288 KB
1_28.txt 2120 ms 204860 KB
1_29.txt 2137 ms 345544 KB
1_30.txt 2122 ms 239780 KB
1_31.txt 2136 ms 377768 KB
1_32.txt 2124 ms 239944 KB
1_33.txt 2118 ms 164284 KB
1_34.txt 2119 ms 164412 KB
1_35.txt 2182 ms 404808 KB
1_36.txt 2125 ms 216816 KB
1_37.txt 2118 ms 164284 KB
1_38.txt 2120 ms 164284 KB
1_39.txt 2125 ms 217156 KB
1_40.txt 2131 ms 284104 KB
1_41.txt 2129 ms 260680 KB
1_42.txt 2131 ms 278984 KB
1_43.txt 2136 ms 329288 KB
1_44.txt 2127 ms 275272 KB
1_45.txt 2131 ms 278728 KB
1_46.txt 2131 ms 284872 KB
1_47.txt 2131 ms 279496 KB
1_48.txt 2134 ms 310088 KB
1_49.txt 2131 ms 277320 KB
1_50.txt 2131 ms 280904 KB
1_51.txt 2131 ms 278984 KB
1_52.txt 2131 ms 278984 KB
1_53.txt 2131 ms 281800 KB
1_54.txt 2131 ms 288328 KB
1_55.txt 2135 ms 327240 KB
1_56.txt 2134 ms 312520 KB
1_57.txt 2131 ms 280136 KB
1_58.txt 2131 ms 280136 KB
1_59.txt 2131 ms 278216 KB
1_60.txt 2131 ms 280648 KB
1_61.txt 2131 ms 283976 KB
1_62.txt 2127 ms 282696 KB
1_63.txt 2131 ms 277448 KB
1_64.txt 2131 ms 279880 KB
1_65.txt 2131 ms 283848 KB
1_66.txt 2131 ms 278856 KB
1_67.txt 2130 ms 304072 KB
1_68.txt 2131 ms 278600 KB
1_69.txt 2133 ms 307656 KB
1_70.txt 2131 ms 281416 KB
1_71.txt 2133 ms 304584 KB