AtCoder Beginner Contest 005

Submission #7472925

Source codeソースコード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>> d(n,vector<int>(n));
    rep(i,n) rep(j,n) cin>>d[i][j];
    
    vector<vector<int>> s(n+1,vector<int>(n+1,0));
    rep(i,n) rep(j,n){
        s[i+1][j+1]=s[i][j+1]+s[i+1][j]-s[i][j]+d[i][j];
    }
    
    vector<int> ans(3000,0);
    FOR(x,1,n){
        FOR(y,1,n){
            rep(u,n-x+1){
                rep(v,n-y+1){
                    int nx=x+u;
                    int ny=y+v;
                    ans[x*y]=max(ans[x*y],s[nx][ny]-s[u][ny]-s[nx][v]+s[u][v]);
                }
            }
        }
    }
    rep(i,2999) ans[i+1]=max(ans[i+1],ans[i]);
    
    int q;
    cin>>q;
    vector<int> p(q);
    rep(i,q) cin>>p[i];
    rep(i,q) cout<<ans[p[i]]<<endl;
}

Submission

Task問題 D - おいしいたこ焼きの焼き方
User nameユーザ名 gyouzasushi
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1170 Byte
File nameファイル名
Exec time実行時間 9 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 50 / 50 sub0.txt,sub1.txt,sub2.txt,sub_rand_max0.txt,sub_rand_max1.txt,sub_rand_max2.txt,sub_rand_max3.txt,sub_rand_min0.txt,s1.txt,s2.txt,sub0.txt,sub1.txt,sub2.txt,sub_rand_max0.txt,sub_rand_max1.txt,sub_rand_max2.txt,sub_rand_max3.txt,sub_rand_min0.txt
Subtask2 50 / 50 rand0.txt,rand1.txt,rand2.txt,rand3.txt,rand4.txt,rand_max0.txt,rand_max1.txt,rand_max2.txt,rand_max3.txt,rand_max4.txt,s1.txt,s2.txt,sub0.txt,sub1.txt,sub2.txt,sub_rand_max0.txt,sub_rand_max1.txt,sub_rand_max2.txt,sub_rand_max3.txt,sub_rand_min0.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
rand0.txt AC 3 ms 256 KB
rand1.txt AC 4 ms 256 KB
rand2.txt AC 6 ms 256 KB
rand3.txt AC 2 ms 256 KB
rand4.txt AC 1 ms 256 KB
rand_max0.txt AC 9 ms 256 KB
rand_max1.txt AC 9 ms 256 KB
rand_max2.txt AC 9 ms 256 KB
rand_max3.txt AC 9 ms 256 KB
rand_max4.txt AC 9 ms 256 KB
s1.txt AC 1 ms 256 KB
s2.txt AC 1 ms 256 KB
sub0.txt AC 1 ms 256 KB
sub1.txt AC 1 ms 256 KB
sub2.txt AC 1 ms 256 KB
sub_rand_max0.txt AC 1 ms 256 KB
sub_rand_max1.txt AC 1 ms 256 KB
sub_rand_max2.txt AC 1 ms 256 KB
sub_rand_max3.txt AC 1 ms 256 KB
sub_rand_min0.txt AC 1 ms 256 KB