#1157419 (C++23) No.3512 moesode

• 問題: No.3512 moesode
• ユーザー: Germanium32
• 提出日時: 2026-04-15 16:32:35
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,743 bytes
• コンパイル時間: 2,360 ms
• コンパイル使用メモリ: 337,348 KB
• 実行使用メモリ: 7,976 KB
• 最終ジャッジ日時: 2026-04-24 20:52:10
• 合計ジャッジ時間: 5,816 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
other	AC * 12 WA * 18

ソースコード

#include <bits/stdc++.h>
#include <queue>
using namespace std;
using ll=long long;
//Aをソート:sort(A.begin(),A.end());
/*二分探索で0以上n未満の中でm以上の最大のiを得る時、
A[n]の形で宣言した場合、lower_bound(A,A+n,m)-A;
vector<int> A(n)の形で宣言した場合、lower_bound(A.begin(),A.end(),m)-A.begin();*/
//char型は0~255までしか持つことができない
//bitのor演算はx|yで表す
//配列の要素数間違えない
//priority_queueは大きい順に取るようになっている
//priority_queue<int,vector<int>,greater<int>> T;で小さい順に取るようにする
//p[i]=make_pair(a,b)みたいな感じで代入
//2のi乗は(1<<i)で表す
//if(b/(1<<i)%2==1)で,bの下からi番目のbitが立っているか
//int型の最大値は2147483647(2^31-1)
//long long型の最大値は2^63-1(大体9e18)
//set上の2分探索 auto it=s.lower_bound(7); みたいにやる
//it--;で添字がずれるが、出力はできない
//*itで値を得る、添字を得たい時はs.order_of_key(x)を使う
struct UnionFind{
  //親と頂点数を表す
  int par[1200000],siz[1200000];
  void make(int n){
    for(int i=0; i<n; i++){
      par[i]=-1;
      siz[i]=1;
    }
  }
  int root(int x){
    while(true){
      if(par[x]==-1){
        break;
      }
      x=par[x];
    }
    return x;
  }
  int count(int y){
    return siz[root(y)];
  }
  void merge(int u,int v){
    int root1=root(u);
    int root2=root(v);
    if(root1==root2){
      return;
    }
    if(siz[root1]>siz[root2]){
      par[root2]=root1;
      siz[root1]+=siz[root2];
    }
    else{
      par[root1]=root2;
      siz[root2]+=siz[root1];
    }
  }
  bool check(int u,int v){
    if(root(u)==root(v)){
      return true;
    }
    else{
      return false;
    }
  }
};
ll modpow(ll a,ll n,ll p){
  if (n == 0){
    return 1; // 0乗にも対応する場合
  }
  if (n == 1){
    return a % p;
  }
  if (n % 2 == 1){
    return (a*modpow(a,n-1,p))%p;
  }
  ll t=modpow(a,n/2,p);
  return (t*t)%p;
}
struct Segsum{
  //datは1indexed
  int dat[1000000],siz=1;
  void make(int n){
    siz=1;
    while(siz<n){
      siz*=2;
    }
    for(int i=0; i<siz*2-1; i++){
      dat[i]=0;
    }
  }
  void change(int pos,int x){
    pos+=siz-1;
    dat[pos]=x;
    while(pos>=2){
     pos/=2;
     dat[pos]=dat[2*pos]+dat[2*pos+1];
    }
  }
  int query(int l, int r, int a, int b, int u){
    if(r<=a || b<=l){
      return 0;
    }
    if(l<=a && b<=r){
      return dat[u];
    }
    int m=(a+b)/2;
    int ansL=query(l,r,a,m,2*u);
    int ansR=query(l,r,m,b,2*u+1);
    return (ansL+ansR);
  }
};
struct Segmax{
  //datは1indexed
  int dat[1000000],siz=1;
  void make(int n){
    siz=1;
    while(siz<n){
      siz*=2;
    }
    for(int i=0; i<siz*2-1; i++){
      dat[i]=0;
    }
  }
  void change(int pos,int x){
    pos+=siz-1;
    dat[pos]=x;
    while(pos>=2){
     pos/=2;
     dat[pos]=max(dat[2*pos],dat[2*pos+1]);
    }
  }
  int query(int l, int r, int a, int b, int u){
    if(r<=a || b<=l){
      return -1e9;
    }
    if(l<=a && b<=r){
      return dat[u];
    }
    int m=(a+b)/2;
    int ansL=query(l,r,a,m,2*u);
    int ansR=query(l,r,m,b,2*u+1);
    return max(ansL,ansR);
  }
};
int main(){
  int n,m,k; cin>>n>>m>>k;
  int c[n],d[n];
  for(int i=0; i<m; i++){
    int a,b; cin>>a>>b;
    c[a-1]++; d[b-1]++;
  }
  int memo=0;
  for(int i=0; i<n; i++){
    if(c[i]!=0){
      memo++;
    }
  }
  ll ans=0;
  vector<int> e;
  for(int i=0; i<n; i++){
    if(c[i]!=0){
      ans+=max(0,k-d[i]);
    }
    else{
      e.push_back(max(0,k-d[i]));
    }
  }
  sort(e.begin(),e.end());
  if(memo<=k){
    memo=k+1-memo;
    for(int i=0; i<memo; i++){
      ans+=e[i];
    }
  }
  cout<<ans<<endl;
}