結果

問題 No.655 E869120 and Good Triangles
コンテスト
ユーザー vjudge1
提出日時 2025-07-26 22:04:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,394 bytes
コンパイル時間 1,648 ms
コンパイル使用メモリ 168,924 KB
実行使用メモリ 364,296 KB
最終ジャッジ日時 2025-07-26 22:04:14
合計ジャッジ時間 14,025 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 WA * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:30:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   30 |         auto [x,y]=q.front();
      |              ^
main.cpp:32:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   32 |         for(auto [dx,dy]:f){
      |                  ^
main.cpp:17:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |     scanf("%d%d%lld",&n,&k,&p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
main.cpp:25:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4005;
const int f[6][2]={{0,1},{0,-1},{-1,-1},{-1,0},{1,0},{1,1}};
int n,k;
ll p;
int d[N][N];
queue<pair<int,int>> q;
ll s1[N][N],s2[N][N];
ll ans;
int mi[N][N];
inline bool ch(int x,int y,int d){
    return (s1[x][y]-s2[x][y+1]-s1[x+d][y]+s2[x+d][y+1+d])>=p;
}
int main(){
    scanf("%d%d%lld",&n,&k,&p);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i;++j){
            d[i][j]=0x3f3f3f3f;
        }
    }
    while(k--){
        int x,y;
        scanf("%d%d",&x,&y);
        d[x][y]=0;
        q.emplace(x,y);
    }
    while(!q.empty()){
        auto [x,y]=q.front();
        q.pop();
        for(auto [dx,dy]:f){
            int tx=x+dx,ty=y+dy;
            if(tx<=0||ty<=0)continue;
            if(tx>n||ty>tx)continue;
            if(d[tx][ty]!=0x3f3f3f3f)continue;
            d[tx][ty]=d[x][y]+1;
            q.emplace(tx,ty);
        }
    }
    for(int i=n;i;--i){
        for(int j=n;j;--j){
            s1[i][j]=s1[i+1][j]+s1[i][j+1]-s1[i+1][j+1]+d[i][j];
            s2[i][j]=s2[i+1][j+1]+s2[i][j+1]-s2[i+1][j+2]+d[i][j];
        }
    }
    for(int i=n;i;--i){
        for(int j=1;j<=i;++j){
            mi[i][j]=min(mi[i+1][j],mi[i+1][j+1])+1;
            while(mi[i][j]!=1&&ch(i,j,mi[i][j]))--mi[i][j];
            ans+=(n-i+1)-mi[i][j];
        }
    }
    printf("%lld\n",ans);
    return 0;
}
0