akhauriyash/Code-Regression huggingface dataset:
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}
template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}
template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}
const ll INF = 1e18;
template <typename T>
T pow(T a, long long n, T e = 1) {
    T ret = e;
    while (n) {
        if (n & 1) ret *= a;
        a *= a;
        n >>= 1;
    }
    return ret;
}

bool memo[100000][11];//点、深さ
VV<> G(100000);
ll color[100000];

void dfs(ll p, ll dep, ll col){
    if(memo[p][dep]) return;
    memo[p][dep] = true;
    if(!dep){
		color[p] = col;
		return;
    }
    dfs(p, dep - 1, col);
    for(auto v:G[p]) dfs(v, dep - 1, col);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    REP(i, 100000)REP(j, 11) memo[i][j] = 0;
    ll n, m; cin >> n >> m;
    REP(i, m){
        ll a, b; cin >> a >> b; a--; b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    ll q; cin >> q;
    V<> v(q), d(q), c(q);
    REP(i, q) cin >> v[i] >> d[i] >> c[i];
    RREP(i, q) dfs(v[i] - 1, d[i], c[i]);
    REP(i, n) cout << color[i] << endl;
}


Measured memory_bytes: 13588
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n;
int p[200100];
int rev[200100];

int solve() {
    for (int i = 0; i < n; i++) {
        rev[p[i]] = i;
    }
    int res = inf;
    int idx = 0;
    while (idx < n) {
        int c = 1;
        while (idx+1<n && rev[idx] < rev[idx+1]) {
            idx++;
            c++;
        }
        res = min(res, n-c);
        idx++;
    }
    return res;
}

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    cout << solve() << endl;
}


Measured memory_bytes: 1792
N, M, C = list(map(int, input().split()))
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
count = 0

for i in range(N):
    sum = 0
    for j in range(M):
        sum += A[i][j] * B[j]
    sum += C
    if(sum > 0):
        count += 1

print(count)


Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#define pq priority_queue
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;

const int iinf = 1 << 29;
const long long linf = 1ll << 61;


int main(){
  ll N,M;
  cin>>N>>M;
  if(N==1){
    if(M==2){cout<<0<<endl;return 0;}
    if(M==1){cout<<1<<endl;return 0;}
    cout<<M-2<<endl;
    return 0;
  }
  if(M==1){
    if(N==2){cout<<0<<endl;return 0;}
    cout<<N-2<<endl;
    return 0;
  }
  cout<<(M-2)*(N-2)<<endl;
  return 0;
}


Measured memory_bytes: 256
use std::io;
use std::cmp::Ordering;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let vec: Vec<i32> = s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
    let (a, b) = (vec[0], vec[1]);

    let d: i32 = a / b;
    let r: i32 = a - b * d;
    let f: f64 = a as f64 / b as f64;
    println!("{} {} {}", d, r, f);
}



Measured memory_bytes: 5044
function main(input) {
  const formatted_input = input.split(' ').map(x => parseInt(x));

  const A = formatted_input[0];
  const B = formatted_input[1];
  const T = formatted_input[2];

  var TT = T+0.5;
  TT = TT - TT%A;

  var result = (TT/A)*B;
  result = parseInt(result, 10);

  console.log(result);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));




Measured memory_bytes: 7372
#include <iostream>
using namespace std;
int main(void){
    int m = 0, f = 0, r = 0, sum;
    char result;
    for (;;)
    {
        cin >> m >> f >> r;
        if (m == -1 && f == -1 && r == -1)
            break;
        if (m == -1 || f == -1)
        {
            result = 'F';
        }
        else
        {   
            sum = m + f;
            if (sum >= 80)
            {
                result = 'A';
            }
            else if (sum >= 65)
            {
                result = 'B';
            }
            else if (sum >= 50)
            {
                result = 'C';
            }
            else if (sum >= 30)
            {
                if (r >= 50)
                {
                    result = 'C';
                }
                else
                {
                    result = 'D';
                }
            }
            else
            {
                result = 'F';
            }
        }
        
        cout << result << endl;
    }
}

Measured memory_bytes: 3088
S=input()
O = ["R","U","D"]
E = ["L","U","D"]

for k in range(len(S)):
    if k%2 == 0:
        if S[k] not in O:
            print("No")
            exit(0)
    else:
        if S[k] not in E:
            print("No")
            exit(0)
print("Yes")


Measured memory_bytes: 39856
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <functional>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(...) ;
#else
#define debug(...) cerr << __LINE__ << " : " << #__VA_ARGS__ << " = " << _tostr(__VA_ARGS__) << endl;

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v);

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}

void _tostr_rec(ostringstream &oss) {
  oss << "\b\b \b";
}

template<typename Head, typename... Tail>
void _tostr_rec(ostringstream &oss, Head &&head, Tail &&... tail) {
  oss << head << ", ";
  _tostr_rec(oss, forward<Tail>(tail)...);
}

template<typename... T>
string _tostr(T &&... args) {
  ostringstream oss;
  int size = sizeof...(args);
  if (size > 1) oss << "{";
  _tostr_rec(oss, forward<T>(args)...);
  if (size > 1) oss << "}";
  return oss.str();
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 210


int N, conn[SIZE][SIZE];
int dist[SIZE][SIZE];

bool visited[SIZE], color[SIZE];
bool dfs(int now, bool c = false) {
  assert(!visited[now]);
  color[now] = c;
  visited[now] = true;

  for (int i = 0; i < N; i++) {
    if (!conn[now][i]) continue;
    if (visited[i]) {
      if (color[i] == c) return false;
    } else {
      if (!dfs(i, !c)) return false;
    }
  }

  return true;
}

int main() {
  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      scanf("%1d", conn[i] + j);
      dist[i][j] = conn[i][j] ? 1 : INF;
    }
    dist[i][i] = 0;
  }

  bool ok = dfs(0);

  if (!ok) {
    puts("-1");
    return 0;
  }

  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
      }
    }
  }

  int ans = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      ans = max(ans, dist[i][j]);
    }
  }

  printf("%d\n", ans + 1);

  return 0;
}

Measured memory_bytes: 4176
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        n: u32,
        x: u32,
        t: u32
    }
    if n % x == 0 {
        println!("{}", (n / x) * t);
    } else {
        println!("{}", (n / x + 1) * t);
    }
}


Measured memory_bytes: 2172
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int sc;
	while(cin>>sc){
		if(sc<1200){
			cout<<"ABC"<<endl;
			continue;
		}
		if(sc<2800){
			cout<<"ARC"<<endl;
			continue;
		}
		else{
			cout<<"AGC"<<endl;
			continue;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

ll dp[6000][6000];
int p[6000];

int main(){
	int n,a,b;cin>>n>>a>>b;
	rep(i,n)scanf("%d",&p[i]);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	rep(i,n)rep(j,n+1){
		if(dp[i][j]==INF)continue;
		if(j>p[i]){
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]+b);
		}
		else{
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a);
			dp[i+1][p[i]]=min(dp[i+1][p[i]],dp[i][j]);
		}
	}
	cout<<*min_element(dp[n],dp[n]+n+1)<<endl;
}

Measured memory_bytes: 281472
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const double PI=3.14159265358979323846;
const int64_t waru = 1000000007;
const in INF=1<<30;
using vec = vector<vector<in>>;

int main(){
char x;
  cin>>x;
  char y=x+1;
  cout<<y;
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;

typedef long long ll;

const ll Inf = 1000000000000000ll;
const int MAXN = 2010;

ll a[MAXN << 1], mn[MAXN][MAXN];

inline ll Min(ll a, ll b){return a < b ? a : b;}

inline void chkmin(ll& a, ll b){if (b < a) a = b;}

int main(){
	int N; ll x;
	scanf("%d %lld", &N, &x);
	for (int i = 1; i <= N; ++i){
		scanf("%lld", &a[i]), a[N + i] = a[i];
		mn[i][0] = a[i];
	}
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j < N; ++j)	
			mn[i][j] = Min(mn[i][j - 1], a[N + i - j]);
	ll ans = Inf, tmp;
	for (int i = 0; i < N; ++i){
		tmp = x * i;
		for (int j = 1; j <= N; ++j)
			tmp += mn[j][i];
		chkmin(ans, tmp);
	}
	printf("%lld", ans);
	return 0;
}


Measured memory_bytes: 31616
<?php
error_reporting(0);
$stdin = file_get_contents('php://stdin');
$line = explode("\n",$stdin);
$fi = 0;
$cnt = 0;
$list = array();
$key = new stdclass();
foreach($line as $l) {
  if (strlen($l)==0) continue;
  if ($fi == 0) {
    $a = explode(" ",$l);
    $key->A = $a;
    $fi++;
    continue;
  }
  if ($fi > 0) {
    $a = explode(" ",$l);
    $key->X[] = $a;
  }
}
$v = preg_replace('/(W+)/','W',$key->A[0]);
$v = preg_replace('/(B+)/','B',$v);
if (chk($v)) {
  printf("%d\n",0);
  exit;
}
printf("%d\n",strlen($v)-1);
exit;
//先頭に違う色の石を足してOKになるか調べる
$r1 = min(solv($v),solv(strrev($v)));
printf("%d\n",$r1);
function chk($r) {
  $len = strlen($r);
  $w = 0;
  $b = 0;
  for($i=0;$i<$len;$i++) {
    if ($r[$i]=='W') $w++;
    else $b++;
  }
  if ($b == 0 || $w == 0) return true;
  return false;
}
function solv($v) {
  $f=0;
while(1) {
  $len  = strlen($v);
  if ($v[0]=='W') {
    $new = 'B';
  }
  else {
    $new = 'W';
  }
  for($i=0;$i<$len;$i++) {
    if ($v[$i]==$new) {
      break;
    }
    else {
      $v[$i]=$new;
    }
  }
  $v = $new . $v;
  $f++;
  //同じ色になったか？
  if (chk($v)) break;
}
return $f;
}


Measured memory_bytes: 4344
#include <iostream>
#include <list>
#include <string>

using namespace std;

int main(){
  string str;
  string temp;
  int m;
  int h;

  while(true){
    cin >> str;
    if( str == "-"){
      break;
    }
    cin >> m;
    for( int i = 0; i < m; ++i){
      cin >> h;
      temp = str.substr( 0, h);
      str += temp;
      str.erase(str.begin(), str.begin()+h);
    }
    cout << str << endl;
  }
  return 0;
}

Measured memory_bytes: 3136
M=1000000007
N=gets.to_i
s1=gets.chomp
s2=gets.chomp
r=s1[0]==s2[0]?3:6
(N-1).times{|i|
    if s1[i]==s2[i]
        r*=2
    else
        if s1[i]!=s1[i+1]&&s1[i+1]!=s2[i+1]
            r*=3
        end
    end
    r%=M
}
puts r


Measured memory_bytes: 14260
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

int pw[10][10]={};
int pwr(int a,int b){
  if(b==0) return 1;
  if(pw[a][b]==0) pw[a][b]=a*pwr(a,b-1);
  return pw[a][b];
}

int main(){
  int n,N,I,ans=1e6,kari;
  cin>>n;
  fr(i,2*pwr(9,4)){
    I=i;N=n;
    kari=0;
    Fr(j,5){
      kari+=I%9;
      N-=(I%9)*pwr(9,j);
      I/=9;
    }
    if(N<0) break;
    fr(j,7){
      kari+=N%6;
      N-=N%6;
      N/=6;
    }
    ans=min(ans,kari);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  int a = s[0] - '0';
  int b = s[1] - '0';
  int c = s[2] - '0';
  int d = s[3] - '0';
  
  for (int bit = 0; bit < (1<<3); bit++) {
    int sum = a;
    
    if (bit & 1) sum += b;
    else sum -= b;
    
    if (bit & (1<<1)) sum += c;
    else sum -= c;
    
    if (bit & (1<<2)) sum += d;
    else sum -= d;
    
    if (sum == 7) {
      cout << a;
      
      if (bit & 1) cout << '+';
      else cout << '-';
      
      cout << b;
      
      if (bit & (1<<1)) cout << '+';
      else cout << '-';
      
      cout << c;
      
      if (bit & (1<<2)) cout << '+';
      else cout << '-';
      
      cout << d << "=7";
     
      break;
    }
  }
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef vector<int> V;
typedef pair<int, int> pii;

const int N = 1e5;
int a[N];
int main()
{
    int x,y,z;cin>>x>>y>>z;
    if(x==y&&x!=z)cout<<"Yes";
    else if(x==z&&x!=y)cout<<"Yes";
    else if(y==z&&x!=y)cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 256
#include<cstdio>
using ull = unsigned long long;

int main(){
    unsigned N;
    scanf("%u", &N);
    ull answer = 0, cards = 0;
    for (size_t i = 0; i < N; i++)
    {
        ull a;
        scanf("%llu", &a);
        if(a) cards += a;
        else{
            answer += cards >> 1;
            cards = 0;
        }
    }
    answer += cards >> 1;
    printf("%llu\n", answer);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector1d(type,name,...) vector<type>name(__VA_ARGS__)
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll updivide(ll a,ll b){if(a%b==0) return a/b;else return (a/b)+1;}

bool hantei(int &n,vector<int> &vec){
    vector<int> num;
    int d=1;
    while(d<=n){
        num.push_back((n/d)%10);
        d*=10;
    }
    for(int i=0;i<(int)vec.size();i++){
        if(count(all(num),vec[i])>=1){
            return false;
        }
    }
    return true;
}

int main(){
    INT(n,k);
    vector<int> vec(k);
    in(vec);
    while(1){
        if(hantei(n,vec)){
            out(n);
            return 0;
        }
        n++;
    }
}

Measured memory_bytes: 3708
#include "bits/stdc++.h"
using namespace std;
 
////////////// Prewritten code follows. Look down for solution. ////////////////

#define fs first
#define sc second
#define pb push_back
#define len(x) ((int)(x).size())
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;

const ll LINF = 1e18;
const int INF = 1e9;
const int MOD = 1e9+7;

template<typename T> void maxself(T &a, T &b){a = max(a, b);};

/// command for char arrays with spaces -> scanf(" %[^\n]", text);
 
////////////////////////// Solution starts below. //////////////////////////////

int main(){

  fastio;
  string a, b;
  cin >> a >> b;
  int A = len(a), B = len(b);
  vector<vector<int>> dp(A+1, vector<int>(B+1, 0));
  /// dp[i][j] = tamanho da maior subsequencia comum de a[i-1] ate b[j-1]
  for(int i = 1; i <= A; i++){
  	for(int j = 1; j <= B; j++){
  		if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
  		else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  	}
	}
	string ans = "";
	int x = A, y = B;
	while(x > 0 and y > 0){
		if(a[x-1] == b[y-1]){
			ans += a[x-1];
			x--, y--;
		}else if(dp[x-1][y] > dp[x][y-1]) x--;
		else y--;
	}
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 35584
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String str = String.valueOf(n);
    int s = str.length();
    int[][][][][] dp = new int[s][2][2][2][2];
    int f = Integer.parseInt(String.valueOf(str.charAt(0)));
    if(f < 3) {
      dp[0][0][0][0][1] = 1;
    } else if(f == 3) {
      dp[0][0][0][0][1] = 1;
      dp[0][1][0][0][0] = 1;
    } else if(f < 5) {
      dp[0][0][0][0][1] = 1;
      dp[0][1][0][0][1] = 1;
    } else if(f == 5) {
      dp[0][0][0][0][1] = 1;
      dp[0][1][0][0][1] = 1;
      dp[0][0][1][0][0] = 1;
    } else if(f < 7) {
      dp[0][0][0][0][1] = 1;
      dp[0][1][0][0][1] = 1;
      dp[0][0][1][0][1] = 1;
    } else if(f == 7) {
      dp[0][0][0][0][1] = 1;
      dp[0][1][0][0][1] = 1;
      dp[0][0][1][0][1] = 1;
      dp[0][0][0][1][0] = 1;
    } else {
      dp[0][0][0][0][1] = 1;
      dp[0][1][0][0][1] = 1;
      dp[0][0][1][0][1] = 1;
      dp[0][0][0][1][1] = 1;
    }

    for(int i = 1; i < s; i++) {
      dp[i][0][0][0][1] = 1;
      for(int j = 0; j < 2; j++) {
        for(int k = 0; k < 2; k++) {
          for(int l = 0; l < 2; l++) {
            dp[i][Math.min(1, j + 1)][k][l][1] += dp[i - 1][j][k][l][1];
            dp[i][j][Math.min(1, k + 1)][l][1] += dp[i - 1][j][k][l][1];
            dp[i][j][k][Math.min(1, l + 1)][1] += dp[i - 1][j][k][l][1];

            int d = Integer.parseInt(String.valueOf(str.charAt(i)));

            if(d < 3) {

            } else if(d == 3) {
              dp[i][Math.min(1, j + 1)][k][l][0] += dp[i - 1][j][k][l][0];
            } else if(d < 5) {
              dp[i][Math.min(1, j + 1)][k][l][1] += dp[i - 1][j][k][l][0];
            } else if(d == 5) {
              dp[i][Math.min(1, j + 1)][k][l][1] += dp[i - 1][j][k][l][0];
              dp[i][j][Math.min(1, k + 1)][l][0] += dp[i - 1][j][k][l][0];
            } else if(d < 7) {
              dp[i][Math.min(1, j + 1)][k][l][1] += dp[i - 1][j][k][l][0];
              dp[i][j][Math.min(1, k + 1)][l][1] += dp[i - 1][j][k][l][0];
            } else if(d == 7) {
              dp[i][Math.min(1, j + 1)][k][l][1] += dp[i - 1][j][k][l][0];
              dp[i][j][Math.min(1, k + 1)][l][1] += dp[i - 1][j][k][l][0];
              dp[i][j][k][Math.min(1, l + 1)][0] += dp[i - 1][j][k][l][0];
            } else {
              dp[i][Math.min(1, j + 1)][k][l][1] += dp[i - 1][j][k][l][0];
              dp[i][j][Math.min(1, k + 1)][l][1] += dp[i - 1][j][k][l][0];
              dp[i][j][k][Math.min(1, l + 1)][1] += dp[i - 1][j][k][l][0];
            }
          }
        }
      }

    }
    
    System.out.println(dp[s - 1][1][1][1][0] + dp[s - 1][1][1][1][1]);
  }
}

Measured memory_bytes: 21844
#include<iostream>
#include<cstring>
#include<vector>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<utility>
#include<climits>
#include<set>
using namespace std;
#define ll long long

void solve(){

	int k;
	cin>>k;
	while(k--)
	{
		cout<<"ACL";
	}
}
int main(){ 
	ios_base::sync_with_stdio(false);
	    cin.tie(0);
	    cout.tie(0);
	    
	#ifndef ONLINE_JUDGE
	    freopen("input.txt","r",stdin);
	    freopen("output.txt","w",stdout);
	#endif


	    int t=1;
//        cin>>t;
        for(int i=1;i<=t;i++){
//            cout<<"Case #"<<i<<": ";
            solve();
        }
        return 0;

}


Measured memory_bytes: 3564
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long ll;

int main()
{
    int N;
    cin >> N;
    map<ll, int> mp;
    ll a;
    for (int i = 0; i < N; i++)
    {
        cin >> a;
        if (mp.find(a) == mp.end())
            mp[a] = 1;
        else
            mp[a] += 1;
    }

    int ans = 0;
    for (auto x : mp)
    {
        if (x.second % 2 == 1)
            ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 6528
#include<stdio.h>
int main()
{
int n,i;
scanf("%d",&n);
if((n==1) || (n==10) || (n==100) )
printf("1");
if ((n==11) || (n==101) || (n==110))
printf("2");
if (n==111)
printf("3");
if(n==0)
printf("0");
return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int, int> P;


signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

	map<int, int> mp;
	int N, M;
	cin >> N;
	int a;
	rep(i,N){
		cin >> a;
		mp[a]++;
	}
	cin >> M;
	int ans = 0;
	rep(i,M){
		cin >> a;
		if(mp[a] == 0) ans++;
		else mp[a]--;
	}
	cout << (ans ? "NO" : "YES") << endl;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
#define int long long

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'

int n, k;

signed main()
{
    cin >> n >> k;
    if (k == 1){
        cout << 0 << endl;
    } else {
        cout << n-k << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=500010;
int tree[N];
int a[N],last[N];
int ans[N];
int n,m;
struct node
{
    int l,r,k;
    bool operator <(const node& o)const
    {
        return r<o.r;
    }
}q[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for(;x<=n;x+=lowbit(x)) tree[x]+=c;
}
int sum(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=tree[x];
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        q[i]={l,r,i};
    }
    sort(q,q+m);
    int k=1;
    for(int i=0;i<m;i++)
    {
        for(;k<=q[i].r;k++)
        {
            int x=a[k];
            if(last[x]) add(last[x],-1);
            add(k,1);
            last[x]=k;
        }
        ans[q[i].k]=sum(q[i].r)-sum(q[i].l-1);
    }
    for(int i=0;i<m;i++) printf("%lld\n",ans[i]);
    return 0;
}


Measured memory_bytes: 17392
#include <bits/stdc++.h>
using namespace std;
int a[200010];
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[x]++;
	}
	for (int i=1;i<=n;i++) printf("%d\n",a[i]);
	return 0;
} 

Measured memory_bytes: 4496
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < (int)(n); i++)
//using ll = long long;

int main(){
    int n,a;
    cin >> n;
    vector<int> cnt(n,0);
    rep(i,n-1){
        cin >> a;
        cnt[a-1]++;
    }
    rep(i,n) cout << cnt[i] << endl;
}


Measured memory_bytes: 4048
#include <stdio.h>

int main(){
  int x;
  scanf("%d", &x);
  x=x%10;
  if(x==2||x==4||x==5||x==7||x==9)printf("hon\n");
  else if(x==0||x==1||x==6||x==8)printf("pon\n");
  else if(x==3) printf("bon\n");
}

Measured memory_bytes: 1628
using System;
using System.Collections.Generic;
using System.Linq;

public class Hello{
    public static void Main(){
        var N = int.Parse(Console.ReadLine());
        var hash = new HashSet<int>();
        
        for(var i = 0;i < N;i++){
            var n = int.Parse(Console.ReadLine());
            if(hash.Contains(n)){
                hash.Remove(n);
            }else{
                hash.Add(n);
            }
        }
        Console.WriteLine(hash.Count);
    }
}


Measured memory_bytes: 19420
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

func main() {
	sc = initScanner(os.Stdin)
	x1, y1, x2, y2 := scanInt(sc), scanInt(sc), scanInt(sc), scanInt(sc)

	x := x2 - x1
	y := y2 - y1

	fmt.Printf("%d %d %d %d", x2-y, y2+x, x1-y, y1+x)
}

// --------------- BASE DEFINITIONS ---------------

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
	return sc
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func scanIntSlice(sc *bufio.Scanner, n int) []int {
	is := make([]int, n)
	for i := 0; i < n; i++ {
		is[i] = scanInt(sc)
	}

	return is
}

func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1780
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf = 1012345678;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int gcd(int a, int b)
{
  if (a%b==0){
    return(b);
  }
  else{
    return(gcd(b,a%b));
  }
}


int h[110];

int main(){
  int N,K;
  cin >> N >> K;
  int h[N];
  rep(i,N){
    cin >> h[i];
  }
  sort(h,h+N);
  // rep(i,N){
  //   cout << h[i];
  // }
  int ans = inf;
  for(int i = K-1; i < N; i++){
    ans = min(ans,h[i]-h[i-K+1]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
import collections

from scipy.special import comb


n = int(input())
aa = []

for i in range(n):
  s = sorted(input())
  s = [''.join(s)]
  aa.append(*s)

cc = collections.Counter(aa)
c = [c[1] for c in cc.items() if c[1] >1]

ans = 0
for i in range(len(c)):
  ans += comb(c[i], 2, exact=True)
  

print(int(ans))

Measured memory_bytes: 56880
x=int(input())

if 400<=x<=599:
	print(8)
if 600<=x<=799:
	print(7)
if 800<=x<=999:
	print(6)
if 1000<=x<=1199:
	print(5)
if 1200<=x<=1399:
	print(4)
if 1400<=x<=1599:
	print(3)
if 1600<=x<=1799:
	print(2)
if 1800<=x<=1999:
	print(1)

Measured memory_bytes: 8992
def solve():
    N = int(input())
    s = []
    for _ in range(N):
        s.append(input())
    M = int(input())
    t = []
    for _ in range(M):
        t.append(input())

    ans = 0
    for s_i in s:
        tmp = 0
        tmp += s.count(s_i)
        tmp -= t.count(s_i)
        ans = max(ans, tmp)
    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 9048
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <cstdlib>
#include <math.h>

using namespace std;

typedef long long ll;
#define rep(i, n) for(long (i) = 0; (i) < (long) (n); (i)++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,a,b) for(long i=(a);i<(b);i++)
#define rrep1(i,a,b) for(long i=(a);i<=(b);i++)
#define rrrep(i,a,b) for(long i=(a);i>=(b);i--)
#define define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define X first
#define Y second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int> >

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const ll LINF = 1e18;

int printYes() {
    cout << "Yes" << endl;
    return 0;
}

int printNo() {
    cout << "No" << endl;
    return 0;
}

int ans;

int printAns() {
    cout << ans << endl;
    return 0;
}


int pow(int x) {
	if (x == 0) {
		return 1;
	}
	else {
		return pow(x - 1) * 2;
	}
}

int main(int argc, char const *argv[])
{
    string S;
    long long int K;
    cin >> S >> K;
    const char* cstr = S.c_str();
    int a = 0;
    rep(i, 100){
        if(cstr[i] == '1') {
            continue;
        } else {
            a = i;
            break;
        }
    }
    if(a + 1> K) {
        cout << 1;
    } else {
        cout << cstr[a];
    }
    return 0;
}


Measured memory_bytes: 256
from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())

n = I()
s = S()

ans = 0
x = 0

for i in range(n):
    if s[i] == 'I':
        x += 1
        if ans < x:
            ans = x
    else:
        x -= 1

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define inf 10000000
#define mod 30000000
#define omarshagar                    \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL);
using namespace std;

int main()
{
    ll n;
    cin>>n;
    cout<<ceil(n/2.0);
    return 0;
}
/*












 */

Measured memory_bytes: 256
n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        x %= mod
        y *= i
        y %= mod
    return x*pow(y, mod-2, mod)%mod

ans = (pow(2, n, mod)-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    map<string, int> bucket;
    int64_t ans =0;
    for(int i =0; i < N; i++){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        ans += bucket[s];
        bucket[s] ++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 11136
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const long double pi = 3.141592653589793;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repi(i, j, n) for(int i = j;i < n;i++)
#define pb push_back
#define mp make_pair
#define mod 998244353
#define F first
#define S second

char ch;
int A[1 << 20], B[1 << 20], C[1 << 20], N = 1;

int solve(int M) {
  int max_left = 0, max_min = 0;
  int ops = 0;

  for(int i = 1;i < N;i++) {

    if(B[i] && (C[i] + 2*(ops + 1) <= M)) {
      ops += 1;
    }

    int to_add = 2*ops;
    max_min = min(A[i] + to_add, max_min);
    max_left = max(A[i] + to_add, max_left);
  }

  // debug(M);
  // debug(max_min);
  return M - max_min;
}

int main() {

// freopen("input.in","r",stdin);
 //freopen("output.out","w",stdout);

 while(cin>>ch) {
   A[N] = (ch == '1' ? 1 : -1);
   if(ch == '?') B[N] = 1;
   N += 1;
 }

 int Z = A[0];
 for(int i = 1;i < N;i++) {
   A[i] += A[i-1];
   Z = max(Z, A[i]);
 }

 C[N-1] = A[N-1];
 for(int i = N-2;i >= 1;i--) {
   C[i] = max(A[i], C[i+1]);
 }

 // rep(i,4) cout<<A[i+1]<<" "<<B[i+1] << " "<<C[i+1]<<endl;
 cout << min(solve(Z), solve(Z+1)) << endl;

  return 0;
}


Measured memory_bytes: 15360
#include <bits/stdc++.h>


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = rbegin(s); i != rend(s); ++i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.size(); }
template<class T> constexpr T pow2(const T a) { return a * a; }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }
template<typename A, size_t N, typename T>
void fillArray(A(&array)[N], const T& val) { std::fill((T*)array, (T*)(array + N), val); }

double d, n, m;
void solve() {
    cin >> n >> m >> d;
    if (d == 0)
        cout << (m - 1) / n << endn;
    else
        cout << 2 * (m - 1) * (n - d) / (n * n) << endn;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout << flush;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll  = long long;
#define rep(i, j) for (int i = 0; i < (int)(j); i++)
#define repeat(i, j, k) for (int i = (j); i < (int)(k); i++)
#define all(v) v.begin(), v.end()
#define debug(x) cerr << #x << " : " << x << endl

template <class T>
bool set_min(T &a, const T &b) {
    return a > b ? a = b, true : false;
}

template <class T>
bool set_max(T &a, const T &b) {
    return a < b ? a = b, true : false;
}
// vector
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &a : v) is >> a;
    return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (const T &t : v) os << "\t" << t;
    return os << endl;
}
// pair
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &v) {
    return os << "<" << v.first << ", " << v.second << ">";
}

class ModInt {
  public:
    static const ll MOD = 998244353ll;
    ll x;
    ModInt() : x(0){};
    ModInt(ll x) {
        while (x < 0) x += MOD;
        x %= MOD;
        this->x = x;
    }
    ModInt &operator+=(const ModInt &l) {
        x += l.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    ModInt &operator-=(const ModInt &l) {
        x -= l.x;
        if (x < 0) x += MOD;
        return *this;
    }
    ModInt &operator*=(const ModInt &l) {
        x = (x * l.x) % MOD;
        return *this;
    }
    ModInt operator+(const ModInt &l) const { return ModInt(x + l.x); }
    ModInt operator-(const ModInt &l) const { return ModInt(x - l.x); }
    ModInt operator*(const ModInt &l) const { return ModInt(x * l.x); }
};

// @warning rの部分はmodとってはいけない
ModInt pow(const ModInt &n, ll r) {
    if (r == 0) return ModInt(1);
    ModInt ret = pow(n, r / 2);
    ret *= ret;
    if (r % 2 != 0) ret = ret * n;
    return ret;
}

// @waring nはMODと互いに素
ModInt inverse(const ModInt &n) {
    return pow(n, ModInt::MOD - 2);
}

ModInt factorial(const ModInt &n) {
    ll ret = 1;
    for (ll i = n.x; i > 1; i--) {
        ret *= i;
    }
    return ModInt(ret);
}

ostream &operator<<(std::ostream &os, const ModInt &a) {
    os << a.x;
    return os;
}
istream &operator>>(std::istream &is, ModInt &a) {
    is >> a.x;
    return is;
}

const int INF = 1 << 30;
const ll INFL = 1LL << 60;

int main() {
    ll N, M, K;
    cin >> N >> M >> K;

    vector<ll> fact(N + 1), fact2(N + 1);
    fact[0]                        = 1;
    rep(i, N) fact[i + 1]          = (fact[i] * (i + 1)) % ModInt::MOD;
    fact2[N - 1]                   = N - 1;
    rep(i, N - 1) fact2[N - i - 2] = (fact2[N - i - 1] * (N - i - 2)) % ModInt::MOD;

    ModInt ans = 0;
    vector<ll> m1(N + 1);
    m1[0]               = 1;
    rep(i, N) m1[i + 1] = (m1[i] * (M - 1)) % ModInt::MOD;
    rep(i, K + 1) {
        auto a = ModInt(fact2[N - i]) * inverse(fact[i]);
        if (i == 0) a = 1;
        a *= M;
        a *= m1[N - i - 1];
        ans += a;
    }
    cout << ans.x << endl;
    return 0;
}


Measured memory_bytes: 7932
#include <bits/stdc++.h>
using namespace std;

struct prod
{
	long long weight;
	long long value;
};

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin>>n;
    long long W;
    cin>>W;
    prod a[n];
    for(int i=0;i<n;i++)
    {
    	cin>>a[i].weight>>a[i].value;
    }

    long long dp[n+1][W+1];
    for(int i=0;i<=n;i++)
    	dp[i][0]=0;
    for(int i=0;i<=W;i++)
    	dp[0][i]=0;

    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=W;j++)
    	{
    		if(a[i-1].weight<=j)
    		{
    			dp[i][j]=max(dp[i-1][j-a[i-1].weight]+a[i-1].value,dp[i-1][j]);
    		}
    		else dp[i][j]=dp[i-1][j];
    	}
    }

    cout<<dp[n][W];
    

	return 0;
}

Measured memory_bytes: 79232
#include<bits/stdc++.h>
#define ull            unsigned long long int
#define ll             long long int
#define pb(x)          push_back(x)
#define mp(a,b)        make_pair(a,b)
#define li(ini)        for(ull i=ini;;i++)
#define lfi(i,ini,r)   for(ull i=ini;i<r;i++)
#define lfd(i,ini,r)   for(ull i=ini;i>=r;i--)
#define lit(it,v)      for(auto it=v.begin();it!=v.end();it++)
#define l(v)           for(ull b:v)
#define sorta(v)       sort(v.begin(),v.end())
#define sortd(v)       sort(v.begin(),v.end(),greater<>())
#define vf(i)          v[i].first
#define vs(i)          v[i].second
#define fast_io        ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define en             "\n"
#define sr(s)          reverse(s.begin(),s.end())


using namespace std;

vector<ll>v;
vector<ll>s;

int main()
{
    //fast_io

    ll x=0,res=0,t=0,i=0,j=0,m=0,n=0,a=0,b=0,c=0,d=0,sum=0,flag=0,flag1=1,cont=0,k=0;

    cin>>n;
    v.clear();
    s.clear();
    vector<ll>v(n+1,0);
    lfi(i,0,n)
    {
        cin>>x;
        v[x]++;
        s.pb(x);

    }

    l(v)
    {
        if(b>0)
        {

            sum+=(b*(b-1))/2;
        }

    }
    k=sum;

    lfi(i,0,n)
    {
        res=s[i];

        sum-=(v[res]*(v[res]-1))/2;
        v[res]--;

        sum+=(v[res]*(v[res]-1))/2;
        v[res]++;

        cout<<sum<<en;
        sum=k;


    }

    return 0;
}


Measured memory_bytes: 5872
def main():
    n, d, *x = map(int, open(0).read().split())

    cnt = 0
    for j in range(n):
        for i in range(j):
            y = x[i*d:(i+1)*d]
            z = x[j*d:(j+1)*d]
            dist_double = 0
            for cur_y, cur_z in zip(y, z):
                dist_double += (cur_y - cur_z) ** 2
            dist = int(dist_double ** 0.5 + 0.5)
            if dist ** 2 == dist_double:
                cnt += 1

    ans = cnt
    print(ans)
    return()

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <string>

int main(int argc, char **argv)
{
	std::string str;
	size_t apos = 0;
	size_t zpos = 0;
	size_t len = 0;

	std::cin >> str;
	apos = str.find("A");
	zpos = str.rfind("Z");
	len = zpos - apos + 1;

	std::cout << len;

	return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <climits>
#include <cstring>
#include <inttypes.h>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

const int cap = 3002;
int N;
int A[cap];
int64_t dp[cap][cap];


int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf(" %d", &A[i]);
    
    for (int i = 1; i <= N; ++i)
        dp[i][i] = 0;
    for (int span = 1; span <= N; ++span) {
        for (int i = 1; i + span <= N + 1; ++i) {
            int j = i + span;
            if ((span & 1) ^ (N & 1)) {
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1]);
            }
            else {
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1]);
            }
        }
    }
    printf("%" PRId64 "\n", dp[1][N + 1]);
}











Measured memory_bytes: 70016
#include<stdio.h>

#define INF (1<<30)

int adj[100][100],visited[100],c[100],parent[100];

int main(){
	int i,j,n,minCost,minID,ans;	scanf("%d",&n);
	for(i=0;i<n;i++){
		for(j=0;j<n;j++)scanf("%d",&adj[i][j]);
	}

	for(i=1;i<n;i++)c[i]=INF;
	c[0]=0;
	parent[0]=-1;

	while(1){
		minCost=INF;
		for(i=0;i<n;i++){
			if(visited[i]==0 && minCost>c[i]){
				minCost=c[i];
				minID=i;
			}
		}if(minCost==INF)break;

		visited[minID]=1;
		for(i=0;i<n;i++){
			if(visited[i] || adj[minID][i]==-1)continue;

			if(c[i]>adj[minID][i]){
				c[i]=adj[minID][i];
				parent[i]=minID;
			}
		}
	}

	ans=0;
	for(i=1;i<n;i++){
		ans+=adj[parent[i]][i];
	}
	printf("%d\n",ans);

	return 0;
}



Measured memory_bytes: 2048
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
#include <stdio.h>

#define rep(i,m,n) for(unsigned long long int i=(m);i<(n);++i)
#define rem(i,m,n) for(int i=(m);i>(n);--i)
#define MOD 1000000007

using namespace std;

using ll = long long int;
using std::swap;

vector<long long int> v;
vector<long long int> w;

int main() {
	int a, b;
	cin >> a >> b;
	int ans;
	ans = ceil((b - 1.) / (a - 1.));
	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
#include <cmath>
#include <set>
#include <deque> 
#include <string>


using namespace std;

int a, b;
int maxAns;

int main()
{
	scanf("%d%d", &a, &b);
	maxAns = a + b;
	int curAns = a - b;
	if (maxAns < curAns) maxAns = curAns;
	
	curAns = a * b;
	if (maxAns < curAns) maxAns = curAns;
	
	printf("%d\n", maxAns);

			
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int INF = 2e9;
const int MOD = 1e9 + 7;

ll gcd(ll a, ll b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll f(ll x, int c, int d) {
   ll ans = x - x / c - x / d + x / lcm(c, d);
   return ans;
}
int main() {
   ll a, b;
   int c, d;
   cin >> a >> b >> c >> d;
   ll ans = f(b, c, d) - f(a - 1, c, d);
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = INT_MAX / 2;

ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

int main() {
	int N; cin >> N;
	vector<ll> a(N);
	rep(i, N) cin >> a[i];
	ll m = a[0];
	rep(i, N) m = lcm(m, a[i]);
	cout << m << endl;
}


Measured memory_bytes: 3580