akhauriyash/Code-Regression huggingface dataset:
// Cheese

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(int (i) = 0; i < (n); i++)
#define REP(i, m, n) for(int (i) = (m); (i) < (n); (i)++)
#define INF LLONG_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a*b/gcd(a,b);};
int mod(int a,int b){return (a+b-1)/b;};
int month[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a < b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a > b){a=b;return true;}return false;};

int h, w, n;
int Sx, Sy;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
char fld[1010][1010];
int a[1010][1010];
int cx[15], cy[15];

int bfs(int sx, int sy, int gx, int gy) {
	Fill(a, INF);
	queue<P> que;
	que.push(P(sx, sy));
	a[sy][sx] = 0;

	while(que.size()) {
		P p = que.front();
		que.pop();
		rep(i, 4) {
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];
			if(0 <= nx && nx < w && 0 <= ny && ny < h) {
				if(a[ny][nx] == INF && fld[ny][nx] != 'X') {
					a[ny][nx] = a[p.second][p.first] + 1;
					que.push(P(nx, ny));
				}
			}
		}
	}
	return a[gy][gx];
}

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

	cin >> h >> w >> n;
	rep(i, h) {
		string s;
		cin >> s;
		rep(j, s.size()) {
			if(s[j] == 'S') {
				Sx = j;
				Sy = i;
			} else if(isdigit(s[j])) {
				int t = s[j] - '0'; t--;
				cx[t] = j;
				cy[t] = i;
			}
			fld[i][j] = s[j];
		}
	}

	int res = bfs(Sx, Sy, cx[0], cy[0]);

	REP(i, 1, n) {
		res += bfs(cx[i - 1], cy[i - 1], cx[i], cy[i]);
	}

	cout << res << endl;
	// int A, B, C, D;
	// cin >> A >> B >> C >> D;
	// cout << bfs(A, B, C, D) << endl;

	// rep(i, n) {
	// 	cout << "Cheese " << i << " :" << cx[i] << " " << cy[i] << endl;
	// }
	return 0;
}



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

int dx[8] = {0,1,0,-1};
int dy[8] = {1,0,-1,0};

int main(){
    
    string s;
    cin>>s;

    if(s == "SUN"){
        cout<<7<<endl;
    }else if( s == "MON"){
        cout<<6<<endl;
    }else if( s == "TUE"){
        cout<<5<<endl;
    }else if( s == "WED"){
        cout<<4<<endl;
    }else if( s == "THU"){
        cout<<3<<endl;
    }else if( s == "FRI"){
        cout<<2<<endl;
    }else{
        cout<<1<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

def main(N, K, A):
    B = np.maximum(A, 0)
    Acum = np.zeros(N + 1, np.int64)
    Bcum = np.zeros(N + 1, np.int64)
    Acum[1:] = np.cumsum(A)
    Bcum[1:] = np.cumsum(B)
    sum1 = Bcum[:N - K + 1]
    sum2 = Bcum[-1] - Bcum[K:]
    sum3 = Acum[K:] - Acum[:N - K + 1]
    x = sum1 + sum2 + np.maximum(sum3, 0)
    return x.max()

print(main(N, K, A))

Measured memory_bytes: 33664
#include <iostream>
using namespace std;

int main(){
int N, K, numcases;
  
  cin >> N >> K;

  numcases = K;
  for(int i=1; i<N; ++i)
    numcases = numcases * (K-1);
  
  cout << numcases << endl;
  
  return 0;
}

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

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	int *a = new int[N];
	int *b = new int[N];
	int *c = new int[M];
	int *d = new int[M];
	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> c[i] >> d[i];
	}

	int dist, pointnum = 0;
	for (int i = 0; i < N; i++) {
		dist = abs(a[i] - c[0]) + abs(b[i] - d[0]);
		pointnum = 0;
		for (int j = 1; j < M; j++) {
			if (dist > abs(a[i] - c[j]) + abs(b[i] - d[j])) {
				dist = abs(a[i] - c[j]) + abs(b[i] - d[j]);
				pointnum = j;
			}
		}
		cout << pointnum + 1 << endl;
	}
}

Measured memory_bytes: 256
#import pysnooper
#import os,re,sys,operator,math,heapq,string
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)
input=stdin.readline

a,b=map(int,input().split())
print(a+b)


Measured memory_bytes: 6312
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)

long long BASE = 0;
long long MINUS = 0;
string S;
vector<int> vec, vec2;

int main() {
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
		if (i % 2 == 0) BASE += 1LL * (S.size() - i);
		if (S[i] == '0') vec.push_back(i + 1);
	}
	for (int i = 0; i < vec.size(); i++) vec[i] %= 2;

	int cnt = 0;
	for (int i = 0; i < vec.size(); i++) {
		cnt++;
		if (i + 1 == vec.size() || vec[i] != vec[i + 1]) {
			if (cnt <= i || vec[i] == 1) vec2.push_back(cnt);
			cnt = 0;
		}
	}
	for (int i = 0; i < vec2.size(); i++) MINUS += 1LL * ((i / 2LL) + 1LL) * vec2[i];
	
	cout << BASE - MINUS << endl;
	return 0;
}

Measured memory_bytes: 5788
n,b,f[50001];main(a){for(;++a<5e4;)for(b=a;(b+=a)<5e4;)f[b]+=!f[a];for(;~scanf("%d",&n);n&&printf("%d\n",b))for(b=0,a=1;a++<n/2;)f[a]+f[n-a]||b++;}

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

int main() {
  int N;
  cin >> N;
  vector<string> vec(N);
  string S;
  for (int i = 0; i < N; i++) {
    cin >> S;
    vec.at(i) = S;
  }
  sort(vec.begin(), vec.end());
  int counter = 1;
  for (int i = 1; i < N; i++) {
    if (vec.at(i) == vec.at(i-1))
      continue;
    if (vec.at(i) != vec.at(i-1))
      counter++;
  }
  cout << counter << endl;
}

Measured memory_bytes: 9500
/* ただの配列をMaxヒープに変換する */

#include <iostream>
using namespace std;
#define MAX 2000000

int H, A[MAX];

int left(int i) { return 2 * i; } // 左の子
int right(int i) { return 2 * i + 1; } // 右の子

void maxHeapify(int idx_me) {
	int largest;
	int left_child = left(idx_me);
	int right_child = right(idx_me);

	// 左の子、自分、右の子の中で一番大きい値のノードを選ぶ
	if (left_child <= H && A[left_child] > A[idx_me]) {
		largest = left_child; // 右より左の子の方が大きい場合
	}
	else {
		largest = idx_me; // 自分が最も大きい場合
	}

	if (right_child <= H && A[right_child] > A[largest]) largest = right_child; // 自分や左のよりも右の子が大きい場合

	// 最も大きい値が自分ではない場合、左もしくは右の子と入れ替える
	if (largest != idx_me) {
		swap(A[idx_me], A[largest]); // 自分と左右どちらかの子と入れ替え
		maxHeapify(largest); // 再起呼び出し
	}
}

int main() {
	cin >> H;

	for (int i = 1; i <= H; i++) cin >> A[i];

	for (int i = H / 2; i >= 1; i--) maxHeapify(i);

	for (int i = 1; i <= H; i++) {
		cout << " " << A[i];
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 5024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define int int64_t

const int N = 1e5 + 10;
int n, m, a[N], ans = 1e17, cnt, bal, ev[N], add[N];

int dd(int x1, int x2) { /// x1 -> x2
    return (x2 - x1 + m) % m;
}

int dist(int i, int x) { /// i -> i + 1
    return min(dd(a[i], a[i + 1]), 1 + dd(x, a[i + 1]));
}

main() {
    cin >> n >> m;
    rep(i, 0, n) { scanf("%lld", &a[i]); --a[i]; }
    rep(i, 0, n - 1) {
        ++ev[(a[i] + 1) % m];
        --ev[a[i + 1]];
        add[a[i + 1]] += dd(a[i], a[i + 1]) - 1;
        if (a[i] > a[i + 1] && a[i] + 1 < m) cnt++;
    }
    rep(i, 0, n - 1) bal += dist(i, 0);
    rep(i, 0, m) {
        ans = min(ans, bal);
        cnt += ev[i];
        bal += add[i] - cnt;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi acos(-1.0)

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string str;
    set<char> sc;
    cin >> str;
    REP(i, str.size()){
        if(sc.count(str[i]) == 0){
            sc.insert(str[i]);
        }else{
            cout << "no" << "\n";
            return 0;
        }
    }
    cout << "yes" << "\n";
    return 0;
}


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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF = 1e9;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

int compress(vector<int> &X1, vector<int> &X2, int W)
{
    vector<int> tmp;
    for (int i=0; i<(int)X1.size(); i++) {
        for (int d=-1; d<=1; d++) {
            int nx1 = X1[i] + d, nx2 = X2[i] + d;
            if (0 <= nx1 && nx1 <= W) tmp.push_back(nx1); 
            if (0 <= nx2 && nx2 <= W) tmp.push_back(nx2); 
        }
    }

    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

    for (int i=0; i<X1.size(); i++) {
        X1[i] = find(tmp.begin(), tmp.end(), X1[i]) - tmp.begin();
        X2[i] = find(tmp.begin(), tmp.end(), X2[i]) - tmp.begin();
    }

    return tmp.size();
}


void bfs(vector<vector<bool>> &board, int sx, int sy, int W, int H)
{
    board[sy][sx] = true;
    queue<pair<int, int>> Q;
    Q.emplace(sx, sy);

    while (Q.size()) {
        pair<int, int> p = Q.front(); Q.pop();
        int x = p.first, y = p.second;
        rep(i, 4) {
            int nx = x+dx[i], ny = y+dy[i];
            if (!in_range(nx, ny, W, H)) continue;
            if (!board[ny][nx]) {
                Q.emplace(nx, ny);
                board[ny][nx] = true;
            }
        }
    }
}


int main()
{
    int W, H;
    while (cin >> W >> H, W || H) {
        int N; cin >> N;
        vector<int> X1(N), X2(N);
        vector<int> Y1(N), Y2(N);
        rep(i, N) cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];

        W = compress(X1, X2, W) - 1;
        H = compress(Y1, Y2, H) - 1;

        /**
        cerr << "---------------"<< endl;
        cerr << "W, H = " << W << ", " << H << endl;
        for (int i=0; i<X1.size(); i++) {
            cerr << "(" << X1[i] << "," << Y1[i] << "), (" << X2[i] << "," << Y2[i] << ")" << endl;
        }
        cerr << "---------------"<< endl;
        **/
        
        vector<vector<bool>> board(H, vector<bool>(W));
        for (int i=0; i<X1.size(); i++) {
            for (int y=Y1[i]; y<Y2[i]; y++) {
                for (int x=X1[i]; x<X2[i]; x++) {
                    board[y][x] = true;
                }
            }
        }

        /**
        for (int y=0; y<H; y++) {
            for (int x=0; x<W; x++) {
                cerr << board[y][x];
            }
            cerr << endl;
        }
        **/

        int ans = 0;
        for (int y=0; y<H; y++) {
            for (int x=0; x<W; x++) {
                if (!board[y][x]) {
                    ans++;
                    bfs(board, x, y, W, H);
                }
            }
        }

        cout << ans << endl;
    }
}

Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    vector<ll> v(n);

    ll S = 0;
    for(int i=0; i<n; i++){
        cin >> v[i];
        S += v[i];
    }

    ll sum = 0, ans = 1e18;
    for(int i=1; i<n; i++){
        sum += v[i-1];
        ans = min(ans, abs(sum - (S - sum)));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
import numpy as np

N, M, X = map(int, input().split())
C = []
A = np.ndarray((N, M), dtype=int)
for j in range(N):
    c, *a = [int(i) for i in input().split()]
    C.append(c)
    A[j] = a

ans = 10**20
for i in range(2 ** N):
    cost = 0
    sk = np.zeros(M, dtype=int)
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            cost += C[j]
            sk += A[j, :]
    if all(s >= X for s in sk):
        ans = min(ans, cost)

if ans == 10**20:
    print(-1)
else:
    print(ans)


Measured memory_bytes: 27224
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void fastIO(){
  ios_base::sync_with_stdio(0); cin.tie(0);
}


int main(){
  string s;
  cin>>s;
  bool a=s[0]==s[1]||s[1]==s[2]||s[2]==s[3];
  a?cout<<"Bad":cout<<"Good";
}




Measured memory_bytes: 256
#ABC-124-B
N = int(input())
H = list(map(int, input().split()))
ans = 1

for i in reversed(range(1, N)):
    flag = True
    for j in reversed(range(i)):
        if H[j] > H[i]:
            flag = False
            break
    if flag == True:
        ans += 1
        
print(ans)

Measured memory_bytes: 3060
import java.util.Scanner;
import java.lang.Math;

public class Main {

    public static void main(String[] args) {
	// write your code here
        Scanner scanner=new Scanner(System.in);
        int A=scanner.nextInt();
        int B=scanner.nextInt();
        int C=scanner.nextInt();
        int X=scanner.nextInt();
        int Y=scanner.nextInt();
        long min=Long.MAX_VALUE;
        for(int i=0;i<=Math.max(X,Y);i++){
            long price=Math.max(0,X-i)*A+Math.max(0,Y-i)*B+2*C*i;
            if(price<min){
                min=price;
            }
        }
        System.out.println(min);

    }
}


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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

int dp[30][111111];

int main(){
	
	vector<int> v;
	v.push_back(1);
	int tmp = 6;
	while(tmp <= 100000){
		v.push_back(tmp);
		tmp *= 6;
	}
	tmp = 9;
	while(tmp <= 100000){
		v.push_back(tmp);
		tmp *= 9;
	}
	
	for(int i = 0;i <= v.size();i++){
		for(int j = 0;j < 111111;j++){
			dp[i][j] = 1000000000;
		}
	}
	
	dp[0][0] = 0;
	
	for(int i = 0;i < v.size();i++){
		for(int j = 0;j < 111111;j++){
			dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
			if(j + v[i] < 111111){
				dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+1);
				dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i+1][j]+1);
			}
		}
	}
	
	int n;cin >> n;
	
	cout << dp[v.size()][n] << endl;
	
	return 0;
}

Measured memory_bytes: 6400
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

int main(){
  int n,count=0;
  cin>>n;
  int a[1000];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<n-1;i++){
    if(a[i]==a[i+1]) {
      a[i+1]=-1;
      count++;
    }
  }
  cout<<count<<endl;
}


Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))

#sub problem: min cost from 0 to i
memo = []

for i, num in enumerate(H):
  if i == 0:
    memo.append(0)
  elif i == 1:
    memo.append(abs(num - H[i-1]))
  else:
    memo.append(min(abs(num - H[i-2])+ memo[i-2], abs(num - H[i-1]) + memo[i-1]) )
print(memo[-1])

Measured memory_bytes: 13980
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque
inf = 10 ** 18
mod = 10 ** 9 + 7

def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
tmp = factorization(n)
ans=0
judge = [(i*(i+1))//2 for i in range(1,10)]
def getC(x):
    ind = bisect.bisect_left(judge, x)
    if judge[ind] == x:
        return ind+1
    else:
        return ind
for a,b in tmp:
    ans+=getC(b)
print(ans)

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

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> k(m);
    vector<vector<int>> s(m, vector<int>(n));

    rep(i, m) {
        cin >> k.at(i);
        s.at(i).resize(k.at(i));
        rep(j, k.at(i)) {
            cin >> s.at(i).at(j);
            --s.at(i).at(j);
        }
    }
    vector<int> p(m);
    rep(i, m) cin >> p.at(i);

    int c;
    bool ok;
    int ans = 0;

    rep(tmp, (1 << n)) {
        ok = true;
        bitset<10> bit(tmp);

        rep(i, m) {
            c = 0; 
            for(int x: s.at(i)) {
                if (bit.test(x)) {
                    c++;
                }
            }
            if ((c % 2) != p.at(i)) {
                ok = false;
            }
        }

        if (ok) {
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define Ans(f, y, n) if(f) cout << y << endl; else cout << n << endl;
#define int long long
#define INF 1000000000000000000
using namespace std;

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
template<typename T>
void debug(vector<vector<T>> m){ REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl;} }

struct edge{int to, cost;};

class Graph
{
public:
    int N;
    vector<vector<edge>> G;

    Graph(int N): N(N){
        G = vector<vector<edge>>(N, vector<edge>(0));
    }

    void add_edge(int from, int to, int cost = 0){
        G[from].push_back(edge({to, cost}));
    }

    void add_edge2(int v1, int v2, int cost = 0){
        add_edge(v1, v2, cost);
        add_edge(v2, v1, cost);
    }

    //SCC decomposition
    void dfs(int v, vector<bool> &used, vec &vs){
        used[v] = true;
        REP(i, G[v].size()){
            if(!used[G[v][i].to]) dfs(G[v][i].to, used, vs);
        }
        vs.push_back(v);
    }
    void rdfs(int v, int k, vector<bool> &used, vec &cmp){
        used[v] = true;
        cmp[v] = k;
        REP(i, G[v].size()){
            if(!used[G[v][i].to]) rdfs(G[v][i].to, k, used, cmp);
        }
    }
    vec scc(int &k){
        vector<bool> used(N, false);
        vec vs(0), cmp(N);
        REP(i, N){
            if(!used[i]) dfs(i, used, vs);
        }
        //reverse graph
        Graph rG(N);
        REP(v, N) REP(i, G[v].size()) rG.add_edge(G[v][i].to, v, G[v][i].cost);

        fill(used.begin(), used.end(), false);
        k = 0;
        IREP(i, vs.size()){
            if(!used[vs[i]]) rG.rdfs(vs[i], k++, used, cmp);
        }
        return cmp;
    }

};

signed main(){

    int N, M; cin >> N >> M;
    Graph G(N);
    int A, B;
    mat cand(N, vec(0));

    REP(i, N + M - 1){
        cin >> A >> B;
        G.add_edge(A - 1, B - 1, 0);
        cand[B - 1].push_back(A - 1);
    }
    int k;
    vec cmp = G.scc(k);
    //cout << k << endl;
    //REP(i, N) cout << cmp[i] << endl;
    REP(i, N){
        int ans = -1, mm = -1;
        for(int c: cand[i]){
            if(cmp[c] > mm){
                mm = cmp[c];
                ans = c;
            }
        }
        cout << ans + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 19576
n, m = map(int, input().split())
L = [-1]*n

if m == 0 and n == 1:
    print(0)
    exit()

for i in range(m):
    s, c = map(int, input().split())
    s -= 1
    if s == 0 and c == 0:
        if n != 1:
            print(-1)
            exit()
        else:
            L[s] = c
    if L[s] != -1 and L[s] != c:
        print(-1)
        exit()
    L[s] = c

#print(L)
ans = ''
for i in range(n):
    if L[i] == -1:
        if i == 0:
            ans += '1'
        else:
            ans += '0'
    else:
        ans += str(L[i])
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;
#define pb push_back

void solve(){
    int x, y, z; cin >> x>> y >> z;
    swap(x, y);
    swap(x, z);
    cout << x << " " << y << " " << z << endl;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int r = (int)Math.ceil((float)(b-1) / (float)(a-1));
        System.out.println(r);
    }
}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
#define int LL
#define PII pair<int, int>
#define VI vector<int>
#define VPII vector<PII>
#define LL long long
#define LD long double
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
#define SIZ(c) (int)(c).size()
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i)
#define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i)

#define sim template<class n
sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
sim> auto operator << (ostream &p, n y) ->
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type 
{int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << endl;}
sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
sim, class s> void mini(n &p, s y) {if(p>y) p = y;}
sim, class s> void maxi(n &p, s y) {if(p<y) p = y;}
#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif 

#define I(x) #x " =", (x), " "
#define A(a, i) #a "[" #i " =", i, "] =", a[i], " "


int32_t main()
  {
  ios_base::sync_with_stdio(0); 
  char c;
  cin >> c;
  if(c >= 'a')
    {
    cout << "a" << endl;
    }
  else cout << "A" << endl;
  }


Measured memory_bytes: 3644
#include <iostream>
#include <vector>

using namespace std;


int main() {
	int H, W;

	cin >> H >> W;

	vector<vector<char>> grid(H, vector<char>(W));
	vector<vector<int>> horizon(H, vector<int>(W, 0)), vertical(H, vector<int>(W, 0));

	//マップ用意
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> grid[i][j];
		}
	}
	//縦方向の連結成分を計算
	int size = 0;
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			if (vertical[i][j] == 0 && grid[i][j] == '.') {
				//いけるところまで行く
				int k = i + 1;
				size = 1;
				while (k < H && grid[k][j] == '.') {
					size++;
					k++;
				}
				//行けたところまで値を入れる
				k--;
				while (k >= i) {
					vertical[k][j] = size;
					k--;
				}
			}
		}
	}

	//横方向の連結成分を計算
	for (int i = 0; i < W; i++)
	{
		for (int j = 0; j < H; j++)
		{
			if (horizon[j][i] == 0 && grid[j][i] == '.') {
				//いけるところまで行く
				int k = i + 1;
				size = 1;
				while (k < W && grid[j][k] == '.') {
					size++;
					k++;
				}
				k--;
				//行けたところまで値を入れる
				while (k >= i) {
					horizon[j][k] = size;
					k--;
				}
			}
		}
	}

	//各点から照らせる大きさの最大を求める
	int ans = 0;
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			if (ans < horizon[i][j] + vertical[i][j] - 1)
				ans = horizon[i][j] + vertical[i][j] - 1;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 35584
import java.util.Scanner;

public class Main{
	public static void main(String args[]) {
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		int c = 0,buf = 0,ans = 0;;
		for(int i = 0;i < n;i++) {
			c = scn.nextInt();
			if(c ==buf) {
				ans++;
				buf = 0;
			}else {
				buf = c;
			}

		}











		System.out.println(ans);
	}
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;
 
long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n,p[5001];
ll k,ans=-100000000000000,c[5001];
bool f[5001];
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	rep(i,n){
		cin>>p[i];
		p[i]--;
	}
	
	rep(i,n)
	cin>>c[i];
	rep(i,n){
		zero(f);
		ll ans1=-100000000000000,na=c[p[i]],now=p[i],tt=0;
		while(!f[now]&&tt<k){
			tt++;
			f[now]=true;
			ans1=max(ans1,na);
			now=p[now];
			if(!f[now])
			na+=c[now];
		}
		if(tt==k){
			ans=max(ans,ans1);
			continue;
		}
		ans1=max(ans1,k/tt*na);
		int kk=k%tt;
		ll aa=na;
		na=c[p[i]],now=p[i];
		while(kk--){
			ans1=max(ans1,k/tt*aa+na);
			now=p[now];
			na+=c[now];
		}
		kk=tt;
		if(k/tt-1>0){
			ll ans2=(k/tt-1)*aa;
			ll na=c[p[i]],now=p[i];
			while(kk--){
				ans2=max(ans2,(k/tt-1)*aa+na);
				now=p[now];
				na+=c[now];
			}	
			ans1=max(ans1,ans2);
		}
		
		ans=max(ans,ans1);
	}
	cout<<ans;
	re 0;
}

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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var N = input[0];
            var M = input[1];
            var C = input[2];
            var B = ReadArrayInt();
            var ans = 0;
            for (int i = 0; i < N; i++)
            {
                var A = ReadArrayInt();
                var sum = C;
                for (int j = 0; j < M; j++) sum += A[j] * B[j];
                if (sum > 0) ans++;
            }

            Console.WriteLine(ans);
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 13396
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from itertools import combinations_with_replacement
def resolve():
    N, M, Q = lr()
    ans = 0
    rest = []
    tmp = 0
    for i in range(Q):
        rest.append(lr())
    for seq in combinations_with_replacement(range(1, M+1), N):
        tmp = 0
        for i in range(Q):
            a, b, c, d = rest[i]
            if seq[b-1] - seq[a-1] == c:
                tmp += d
        ans = max(tmp, ans)
    print(ans)
resolve()

Measured memory_bytes: 81484
#include <iostream>
#include <cstdio>
#include <cstring>

typedef long long ll;
ll n, x, ans, h[60], p[60];

void sovle(int now)
{
	if (x <= 0) return;
	if (!now)
	{
		--x;
		++ans;
		return;
	}
	if (x >= h[now])
	{
		x -= h[now];
		ans += p[now];
		return;
	}
	--x;
	if (x > 0) sovle(now - 1);
	if (x > 0) ++ans, --x;
	if (x > 0) sovle(now - 1);
	--x;
}

int main()
{
	scanf("%lld%lld", &n, &x);
	h[0] = 1, p[0] = 1;
	for (int i = 1; i <= 50; ++i) h[i] = (h[i - 1] << 1) + 3, p[i] = (p[i - 1] << 1) + 1;
	sovle(n);
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000003;
template <typename Int, Int MOD, int N>
struct comb_util {
	std::array<Int, N + 1> fc, ifc;

	comb_util() {
		fc[0] = 1;
		for (int i = 1; i <= N; i++) fc[i] = fc[i - 1] * i % MOD;
		ifc[N] = inv(fc[N]);
		for (int i = N - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1) % MOD;
	}

	Int fact(Int n) { return fc[n]; }

	Int inv_fact(Int n) { return ifc[n]; }

	Int inv(Int n) { return pow(n, MOD - 2); }

	Int pow(Int n, Int a) {
		Int res = 1, exp = n;
		for (; a; a /= 2) {
			if (a & 1) res = res * exp % MOD;
			exp = exp * exp % MOD;
		}
		return res;
	}

	Int perm(Int n, Int r) {
		if (r < 0 || n < r)
			return 0;
		else
			return fc[n] * ifc[n - r] % MOD;
	}

	Int binom(Int n, Int r) {
		if (n < 0 || r < 0 || n < r) return 0;
		return fc[n] * ifc[r] % MOD * ifc[n - r] % MOD;
	}

	Int homo(Int n, Int r) {
		if (n < 0 || r < 0) return 0;
		return r == 0 ? 1 : binom(n + r - 1, r);
	}
};

using comb = comb_util<long long, 1000003, 1000002>;
comb cb;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	vector<int> res(N);
	int x, d, n;
	for (int i = 0; i < N; i++) {
		cin >> x >> d >> n;
		if (x == 0) {
			res[i] = 0;
		}
		else if (d == 0) {
			res[i] = cb.pow(x, n);
		}
		else {
			int inv = cb.inv(d);
			int a = (x * inv) % MOD;
			int b = a + n - 1;
			if (b >= MOD || a == 0) {
				res[i] = 0;
			}
			else {
				res[i] = cb.fact(b);
				if (a >= 2)res[i] = (res[i] * cb.inv_fact(a - 1)) % MOD;

				res[i] = (res[i] * cb.pow(d, n)) % MOD;
			}
		}

	}

	for (int i = 0; i < N; i++) {
		cout << res[i] << endl;
	}
}

Measured memory_bytes: 18048
from itertools import product

N = int(input())
testimony_by = []   # i番目の人の発言を格納する(3次元リスト)
for i in range(N):
    a = int(input())
    li = []   # 発言一つ分のリスト
    for j in range(a):
        li.append(list(map(int, input().split())))
    testimony_by.append(li)
ans = 0
for bit_li in product([0, 1], repeat=N):
    is_ok = True    # 矛盾がないか
    for i in range(N):
        if bit_li[i] == 1:
            for li in testimony_by[i]:
                x, y = li
                x -= 1
                if bit_li[x] != y:
                    is_ok = False
                    break

        if not is_ok:
            break
    if is_ok:
        ans = max(ans, sum(bit_li))
print(ans)


Measured memory_bytes: 68736
import java.io.*;
import java.util.*;

public class Main {

    private static FastReader in = new FastReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static class Work {
        private final int days;
        private final int reward;

        private Work(int days, int reward) {
            this.days = days;
            this.reward = reward;
        }
    }

    private static void solve() {
        int n = in.nextInt();
        int m = in.nextInt();

        List<Work> works = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            works.add(new Work(in.nextInt(), in.nextInt()));
        }

        works.sort(Comparator.comparingInt(w -> w.days));

        long ans = 0;
        int nextWork = 0;
        Queue<Work> bestWorks = new PriorityQueue<>((w1, w2) -> w2.reward - w1.reward);
        for (int i = 1; i <= m; i++) {
            for (; nextWork < n && works.get(nextWork).days <= i; nextWork++) {
                bestWorks.add(works.get(nextWork));
            }

            Work best = bestWorks.poll();
            if (best == null) continue;

            ans += best.reward;
        }

        out.println(ans);
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        // https://qiita.com/masakinpo/items/5f77f2a879578a85a0bb
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 45272
n = int(input())
g = [[-1 for _ in range(15)] for _ in range(15)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    g[i][x-1] = y
    
ans = 0
for bit in range(1<<n):
  honests = [0]*n
  for i in range(n):
    if bit & 1<<i: honests[i] = 1
  flg = True
  for i in range(n):
    if honests[i]:
      for j in range(n):
        if g[i][j] == -1: continue
        if g[i][j] != honests[j]: flg = False
  if flg:
    ans = max(ans, honests.count(1))
print(ans)

Measured memory_bytes: 9192
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
//using
using namespace std;
/*using vi = vector <int>;
using vs = vector <string>;
using vc = vector <char>;*/
//vector<vector<char> > hyou(N, vector<char>(N));
//define
#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
//グローバル変数宣言
int a=0,b=0,c=0;

signed main(){
    vector<vector<int> > A(3, vector<int>(3));
    vector<vector<bool> > aa(3, vector<bool>(3));
    rep(i,3)rep(j,3)cin>>A[i][j];
    cin>>a;
    vector<int>B(a);
    rep(i,a)cin>>B[i];
    rep(i,3){
        rep(j,3){
            aa[i][j]=false;
            rep(k,a){
                if(A[i][j]==B[k])aa[i][j]=true;}}}
    rep(i,3)if(aa[i][0]==true&&aa[i][1]==true&&aa[i][2]==true)b=1;
    rep(i,3)if(aa[0][i]==true&&aa[1][i]==true&&aa[2][i]==true)b=1;
    if(aa[0][0]==true&&aa[1][1]&&aa[2][2])b=1;
    if(aa[0][2]==true&&aa[1][1]&&aa[2][0])b=1;
    if(b==1)print("Yes") else print("No");
}


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

using namespace std;

#define int long long
#define MOD 1000000007

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}

//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long

int x;

signed main()
{

    cin >> x;

    int y = x % 500;

    int ans = (x / 500) * 1000 + (y / 5) * 5;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n-1; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b) {if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b) {if(a<b) a=b;}

template<typename T>
T gcd(T x, T y) {
    if(x<y) gcd(y,x);
    while(y>0) {
        T tmp = x%y;
        x = y;
        y = tmp;
    }
    return x;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k; cin >> n >> k;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    int g = a[0];
    int m = 0;
    REP(i,n) {
        if(i>0) g = gcd(g,a[i]);
        chmax(m,a[i]);
    }
    bool ans = (k%g==0 && k<=m);
    cout << (ans ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return 0;
}

Measured memory_bytes: 640
n = int(input())
list1 = list(map(int,input().split()))
count = 0
def mizuyari(a,b):
	global count
	global list1
	for i in range(a,b):
		list1[i] -= 1
	count += 1

def search():
	global list1
	flag = 0
	for i in range(n):
		if list1[i] != 0:
			s = i
			break
	for j in range(s+1,len(list1)):
		if list1[j] == 0:
			mizuyari(s,j)
			flag = 1
			break
	if not flag:
		mizuyari(s,len(list1))

if __name__ == "__main__":
	while sum(list1) != 0:
		search()
	print(count)


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

int main() {
  int N;
  cin >> N;

  map<string, int> m;
  rep(i,0,N-1) {
    string s;
    cin >> s;
    m[s]++;
  }

  vector<string> v;
  int n = 0;
  for (pair<string, int> p:m) {
    n = max(n, p.second);
  }

  for (pair<string, int> p:m) {
    if (p.second == n) v.push_back(p.first);
  }

  sort(v.begin(), v.end());

  for (string s:v) cout << s << endl;
  return 0;
}


Measured memory_bytes: 26868
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb push_back
#define REP(i, a, b)  for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i=(a-1), i##end = (b); i >=i##end; --i)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int N = 2000;
const int oo = 0x3f3f3f3f;
const int mo = 1e9 + 7;
 
template<typename T> T read() {
    T n(0), f(1);
    char ch = getchar();
    for( ;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for( ; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48; 
    return n * f;
}

int n, k;
int dp[N + 5][N + 5];

int main() {
#ifdef Wearry
    freopen("data.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
#endif 

    cin >> n >> k;
    dp[1][n - k] = 1;
    for(int i = 2; i <= n; ++i) {
        int sum = 0;
        for(int j = 0; j <= n; ++j) {
            sum = (sum + dp[i-1][j]) % mo;
            dp[i][j] = (sum + dp[i-1][j+1]) % mo;
        }
    }

    int ans = dp[n][0];
    for(int i = 0; i < n - k - 1; ++i) ans = (ans << 1) % mo;

    printf("%d\n", ans);
    return 0;
}


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

std::vector<std::vector<int>> comb(std::vector<int> list, int r)
{
  int i = 0;
  auto result = std::vector<std::vector<int>>{};
  for (auto &&el : list) {
    if (r == 1) {
      result.push_back(std::vector<int>{el});
    } else {
      auto clone = list;
      clone.erase(clone.begin(), clone.begin() + i + 1);
      for (auto &&res : comb(clone, r - 1)) {
        auto rest = res;
        rest.insert(rest.begin(), el);
        result.push_back(rest);
      }
    }
    i++;
  }
  return result;
}

auto range(int n)
{
  auto v = std::vector<int>{};
  for (int i = 0; i < n; i++) {
    v.push_back(i);
  }
  return v;
}

template <typename T>
auto printer(T t)
{
  for (auto &&i : t)
    std::cout << i << ' ';
  std::cout << std::endl;
}

int main(void)
{
  auto s = std::string{};
  std::cin >> s;
  unsigned long long result = std::stoll(s);
  for (int i = 0; i < s.size() - 1; i++) {
    // std::cout << "current i = " << i << std::endl;
    for (auto &&p : comb(range(s.size() - 1), i + 1)) {
      p.insert(p.begin(), -1);
      p.push_back(s.size());
      // if (p.front() != 0) {
      // p.insert(p.begin(), 0);
      // }
      // if (p.back() != s.size() - 1) {
      // p.push_back(s.size() - 1);
      // }
      // p.push_back(s.size());
      // std::cout << "p is ";
      // printer(p);
      for (int idx = 0; idx + 1 < p.size(); idx++) {
        // std::cout << "result += " << s.substr(p[idx] + 1, p[idx + 1] -
        // p[idx])
        // << std::endl;
        result += std::stoll(s.substr(p[idx] + 1, p[idx + 1] - p[idx]));
      }
      // std::cout << "result += " << s.substr(p.back()) << std::endl;
      // result += std::stoi(s.substr(p.back()));
    }
    // std::cout << std::string{"hoge"}.substr(3, 1) << std::endl;
  }
  std::cout << result << std::endl;
}


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

using namespace std;

#define int long long
#define pb push_back
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) FOR(i, n, 0);

int digsum (int n) {
  int sum = 0;
  while(n > 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

signed main () {
  cin.tie(0);
  cout << setprecision(10);

  int n; cin >> n;
  int a = 0, b = 0;
  int mi = INT_MAX;
  FOR(i, 1, n/2+1) {
    a = i; b = n - i;
    mi = min(mi, digsum(a) + digsum(b));
  }
  cout << mi << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <map>
#include <cstdlib>
#include <cctype>
#include <ctype.h>
#define ll long long
using namespace std;
int main()
{

    int k, x;
    cin >> k >> x;
    if (k * 500 >= x)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
}

signed main()
{
    showoff;
    string s,ps = "";
    cin >> s;
    int ans = 0;
    FOR(i,0,sz(s)){
    	if(sz(ps) > 1 || s[i] != ps[0]){
    		ps = s[i];
    		++ans;
    		continue;
    	}
    	if(i+1 < sz(s)){
    		++ans;
    		ps += s[i+1];
    		++i;
    		continue;
    	}
    }
    cout << ans;
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...   

Measured memory_bytes: 720
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define MEM(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int gcd(int a, int b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
int a[114514];
int dp[55][10010];
int main() {
	IOS;
	int n, k;
	cin >> n >> k;
	int g;
	REP(i, n) {
		cin >> a[i];
		if (!i)g = a[i];
		g = gcd(g, a[i]);
	}
	sort(a, a + n);
	if (k > a[n - 1] || k % g != 0) {
		cout << "IMPOSSIBLE" << endl;
		return 0;
	}
	cout << "POSSIBLE" << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	int n ; cin>>n;
  	map<ll,ll> f;
  	ll a[n];
  	for(int i = 0 ;i < n ; i++)
    {
      cin>>a[i];
      f[a[i]]++;
    }
  	ll tot = 0; 
  	for(auto p : f)
    {
      	ll x = p.second;
     	tot+= ((x)*(x-1))/2;
    }
  	for(int i = 0 ; i < n ; i++)
    {
      cout<< tot - (f[a[i]]-1)<<endl;
    }
	return 0;
}

Measured memory_bytes: 12288