akhauriyash/Code-Regression huggingface dataset:
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define set0(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
/*
	Source: AtCoder Beginner Contest 054
	Author: fts2001 (the_silliest)
 */
using namespace std;
int n,ma,mb,a[45],b[45],c[45],dp[45][405][405],ans=INF;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>ma>>mb;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    setINF(dp);
    dp[0][0][0]=0;
    dp[0][a[0]][b[0]]=c[0];
    for(int i=1;i<n;i++){
        dp[i][0][0]=0;
        for(int j=1;j<=400;j++){
            for(int k=1;k<=400;k++){
                dp[i][j][k]=dp[i-1][j][k];
                if(j>=a[i] && k>=b[i])dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-a[i]][k-b[i]]+c[i]);
            }
        }
    }
    for(int i=1;ma*i<=400 && mb*i<=400;i++){
        ans=min(ans,dp[n-1][ma*i][mb*i]);
    }
    if(ans==INF)cout<<"-1\n";
    else cout<<ans<<endl;
    return 0;
}

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

int main(){
    int time;
    int s,m;
    int total=0;
    for(int i=0;i<4;i++){
        cin >> time;
        total += time;
    }
    m = total / 60;
    total %= 60;
    s = total;
    cout << m << endl << s << endl;
}

Measured memory_bytes: 1164
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int[] B = new int[N];
        B[N - 2] = 0;

        for (int i = 0; i < N - 1; i++) {
            B[Integer.parseInt(sc.next()) - 1]++;
        }

        PrintWriter out = new PrintWriter(System.out);
        for (int i = 0; i < N; i++) {
            out.println(B[i]);
            out.flush();
        }

        sc.close();
    }
}

Measured memory_bytes: 61008
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m, d = LI()
    print(2 * (n - d) * (m - 1) / n ** 2 if d else n * (m - 1) / n ** 2)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 38512
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC134_a solver = new ABC134_a();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC134_a {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int r = in.nextInt();
            int tet = (r ^ 2);
            out.println(3 * (int) Math.pow(r, 2));

        }

    }
}



Measured memory_bytes: 21844
#include<stdio.h>
#include<stdlib.h>
#include<stdarg.h>
#include<string.h>
#include<math.h>
#include<limits.h>
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define reps(i,n,k) for((i)=0;(i)<(n);(i)+=(k))
#define MOD ((int)1e9+7)
#define INF INFINITY
typedef long long ll;
typedef unsigned long long ull;
typedef struct pair_{int x,y;}pair_t;
void swap(int *x, int *y){int t=*x;*x=*y;*y=t;}
void debug(char *f, ...){va_list a;va_start(a,f);vfprintf(stderr,f,a);va_end(a);}
int asc_cmp(const void *x, const void *y){int X=*((int*)x),Y=*((int*)y);if(X<Y)return -1;else if(X>Y)return 1;else return 0;}
int desc_cmp(const void *x, const void *y){int X=*((int*)x),Y=*((int*)y);if(X<Y)return 1;else if(X>Y)return -1;else return 0;}
int asc_cmp_str(const void* X,const void* Y){char *x=(char*)X,*y=(char*)Y;return strcmp(x,y);}

int main(){
    int n;scanf("%d",&n);
    char s[300000][20];
    for(int i=0;i<n;i++){
        scanf("%s",s[i]);
    }

    qsort(s,n,sizeof(s[0]),asc_cmp_str);
    int ans=0;
    for(int i=0;i<n-1;i++){
        if(strcmp(s[i],s[i+1])){
            //printf("%s, %s\n",s[i],s[i+1]);  
            ans++;
        }
        //printf("%s\n",s[i]);
    }
    printf("%d\n",ans+1);
}


Measured memory_bytes: 9132
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int N=1e5+5;

int n,k;
int a[N];


int gcd(int a,int b)
{
    int q,temp;
    int r,oldr;

    oldr=a;
    r=b;

    while(r!=0)
    {
        q=oldr/r;

        temp=r;
        r=oldr-q*r;
        oldr=temp;

    }


    return oldr;

}

int abs(int x)
{
    if(x<0)
        return -x;
    return x;
}


int main()
{
   int i;
   int g;
   bool cool=false;

   cin>>n>>k;
   for(i=1;i<=n;i++)
   {
       scanf("%d",&a[i]);
       if(a[i]>=k)
        cool=true;
   }

   if(!cool)
   {
       cout<<"IMPOSSIBLE"<<endl;

       return 0;
   }


   g=a[1];

   for(i=2;i<=n;i++)
       g=gcd(g,a[i]);

   if(k%g==0)
    cout<<"POSSIBLE"<<endl;
   else
    cout<<"IMPOSSIBLE"<<endl;


   return 0;
}

Measured memory_bytes: 640
function calcultateGCD(a,b,res) {
	if(a==b)
		return a*res;
    else if ((a&1)==0 && (b&1)==0) 
    	return calcultateGCD(a>>1, b>>1, res<<1);	
    else if ((a&1)==0) 
    	return calcultateGCD(a>>1, b, res); 
    else if ((b&1)==0) 
    	return calcultateGCD(a, b>>1, res); 
    else if (a>b) 
    	return calcultateGCD(a-b, b, res);
    else 
    	return calcultateGCD(a, b-a, res); 
}

function calcultateLCM(a,b,gcd) {
	  return a*b/gcd;
}

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');

if(lines.length > 50) {
	console.log("Invalid dataset size. Dataset size is "+lines.length+" but must be <= 50");
} else {
	for (var i = 0; i < lines.length; i++) {
		var line = lines[i].trim();
	    if (line == '') break;
	    var vals = line.split(' ').map(function(i){return +i;});
	    if(vals.length != 2 || isNaN(vals[0]) || isNaN(vals[1]) || vals[0] < 0 || vals[0] > 2000000000 || vals[1] < 0 || vals[1] > 2000000000) {
	    	console.log("Invalid dataset: "+line+ ". Use 0 <= a, b <= 2,000,000,000");
	    } else {
	    	var gcd = calcultateGCD(vals[0],vals[1],1);
	    	var lcm = calcultateLCM(vals[0],vals[1],gcd);
	    	if(lcm > 2000000000)
		    	console.log("Invalid dataset: "+line+ ". LCM is "+lcm+" but must be <= 2,000,000,000");
	    	else 
	    		console.log(gcd+" "+lcm);
		}
	}
}

Measured memory_bytes: 15864
#include <stdio.h> 

int main () {
	int n;
	scanf("%d", &n);
	
	int count = 0;
	for (int i = 1; i < 10; i++) {
		for (int j = 1; j < 10; j++) {
			if (i * j == n) {
				count++;
			}
		}
	}
	
	if (count == 0) {
		puts("No");
	}
	else {
		puts("Yes");
	}
	
	return 0;
}

Measured memory_bytes: 1628
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N, Q = input_nums()
    C = [0]*N
    G = [[] for i in range(N)]
    for i in range(N-1):
        a, b = input_nums()
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    for i in range(Q):
        p, x = input_nums()
        C[p-1] += x
    isVisit = [False]*N
    isVisit[0] = True
    stack = [0]

    while stack:
        now = stack.pop()
        for i in G[now]:
            if not isVisit[i]:
                isVisit[i] = True
                stack.append(i)
                C[i] += C[now]
    print(*C)

if __name__ == '__main__':
    main()

Measured memory_bytes: 95744
n, m = map(int, input().split())
klist = []
alist = []
for i in range(n):
    ret = list(map(int, input().split()))
    klist.append(ret[0])
    alist.append(ret[1:])

snum = [0] * m
for i in range(n):
    for j in alist[i]:
        snum[j-1] += 1

print(snum.count(n))


Measured memory_bytes: 3060
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {//
        n:usize,
        mut a:[i64;n],
    }
    let mut mxs = -1;
    let mut ans = 0;
    for &x in a.iter() {
        if mxs > x {
            ans += mxs - x;
        }
        mxs = max(mxs, x);
    }
    println!("{}", ans);
}


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

int main()
{
	int N;
	string buf;
	getline(cin, buf);
	N = stoi(buf);

	for(int i = 0; i < N; i++)
	{
		string str;
		getline(cin, str);

		for(int j = 6; j < str.size(); j++)
		{
			if(str[j] == 'o')
			{
				if(str[j - 1] == 'n' &&
					str[j - 2] == 'i' &&
					str[j - 3] == 'h' &&
					str[j - 4] == 's' &&
					str[j - 5] == 'o' &&
					str[j - 6] == 'H' )
				{
					str[j] = 'a';
				}

			}
		}
		cout << str << endl;

	}
}

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

int main(){
int H1, M1, H2, M2, K;

cin >> H1 >> M1 >> H2 >> M2 >> K;

if (M1 > M2) {
  cout << (H2 - H1 -1)*60 + (M2 + 60 - M1) - K;
}
else{
  cout << (H2 - H1)*60 + (M2 - M1) - K;
}

}

Measured memory_bytes: 3624
H, W = map(int, input().split())

lst = [list(input()) for i in range(H)]
ans = "Yes"
for i in range(H):
  for j in range(W):
    if lst[i][j] == "#":
      above = False
      below = False
      left = False
      right = False
      if (i > 0):
        if (lst[i-1][j] == '#'):
          above = True
      if (j > 0):
        if (lst[i][j-1] == '#'):
          left = True
      if (i < H-1):
        if (lst[i+1][j] == '#'):
          below = True
      if (j < W-1):
        if (lst[i][j+1] == '#'):
          right = True
      if (not above and not below and not left and not right):
        ans = 'No'
        break
print(ans)

Measured memory_bytes: 3064
#include<cstdio>
int main(){
    char s[201];
    scanf("%s",s);
    int ans=0;
    for(int i=1;s[2*i]!='\0';i++){
        bool flag=true;
        for(int j=0;j<i;j++){
            if(s[j]!=s[i+j]){
                flag=false;
                break;
            }
        }
        if(flag)ans=2*i;
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<string.h>
int main(){
  char w[111];
  int i,a[33]={};
  scanf("%s",w);
  for(i=0;i<strlen(w);i++){
    a[w[i]-97]++;
  }
  for(i=0;i<26;i++){
    if(a[i]%2) {
      i=0;
      break;
    }
  }
  puts(i?"Yes":"No");
}

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<bool> A(N+1, false);
    for (int i = 0; i < K; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int a;
            cin >> a;
            A[a] = true;
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (!A[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int main()
{
	string s;
	cin>>s;
	if(s.length()==3){
		for(int i=s.length()-1;i>=0;i--){
		cout<<s[i];
	} 
	}
	else{
		for(int i=0;i<s.length();i++){
			cout<<s[i];
		}
	}
}

Measured memory_bytes: 384
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
t = 1900*m + 100*(n-m)
ans = t * 2**m
print(ans)


Measured memory_bytes: 10048
#include<bits/stdc++.h>
#define PII pair<string,string>
#define LL long long int
using namespace std;
int main()
{

    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    string str, A, B;
    cin >> str;
    for(int i = 0; i < 2 * n; i++)
    {
        if(i < n)
            A+=str[i];
        else
            B+=str[3 * n - i -1];
    }
    map<PII, LL> Maping;
    vector<PII> vv;
    for(int i = 0;  i < (1 << n); i++)
    {
        string gama, sigma, delta, beta;
        for(int j = 0; j < n; j++)
        {
            if((i >> j) & 1)
            {
                gama += A[j];
                sigma += B[j];
            }
            else
            {
                delta += A[j];
                beta += B[j];
            }
        }
        Maping[make_pair(gama, delta)]++;
        vv.push_back(make_pair(sigma,beta));
    }
    LL ans = 0;
    for(auto v : vv)
        ans += Maping[v];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 95980
n = int(input())
x,u = [],[]
for i in range(n):
  X,U = map(str, input().split())
  x.append(float(X))
  u.append(U)
y = 0
b = 0
for i in range(n):
  if u[i] == 'JPY':
    y += x[i]
  else:
    b += x[i]
print(y + b*380000.0)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
// (setq-default c-basic-offset 2)

int main() {
  long long n, x, t;
  cin >> n >> x >> t;

  long long ret = 0;
  long long left = n;
  while (left > 0) {
    ret += t;
    left -= x;
  }
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main(){
  int X,Y,res;
  cin >> X >> Y;
  if (X < 4) res += (4 - X) * 100000;
  if (Y < 4) res += (4 - Y) * 100000;
  if (X == 1 && Y == 1) res += 400000;
  cout << res;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void){
  int N,A,B;
  scanf("%d %d %d",&N,&A,&B);
  if(A*N>B){
    printf("%d\n",B);
  }
  else{
    printf("%d\n",N*A);
  }
  return 0;
}

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

int k[12];
int s[12][12];
int p[12];

int main() {
    int N, M;
    cin >> N >> M;
    rep(i, M) {
        cin >> k[i];
        rep(j, k[i]) {
            cin >> s[i][j];
            s[i][j]--;
        }
    }
    rep(i, M) {
        cin >> p[i];
    }

    int res = 0;
    rep(div, 1<<N) {
        // cout << "here?" << endl;
        bool b = true;
        rep(i, M) {
            int sm = 0;
            rep(j, k[i]) {
                if (div>>s[i][j]&1) sm++;
            }
            if (sm%2!=p[i]) {
                b = false;
                break;
            }
        }
        if (b) res++;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3548
def gcd(a,b):
    if a ==0:
        return b
    if b==0:
        return a
    return gcd(b,a%b)
N = int(input())
A = list(map(int,input().split()))
R = [0]*(N+1)
L = [0]*(N+1)
M = [0]*(N+1)
for i in range(N):
    L[i+1]= gcd(L[i],A[i])
    R[-(i+2)] = gcd(R[-(i+1)],A[-(i+1)])
for i in range(N):
    M[i] = gcd(L[i],R[i+1])
print(max(M))

Measured memory_bytes: 14436
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

int main() {
  int N, M;
  cin >> N >> M;
  Graph G(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  vector<int> dist(N, -1);
  queue<int> que;

  dist[0] = 0;
  que.push(0);

  while (!que.empty()) {
    int v = que.front();
    que.pop();
    for (int nv : G[v]) {
      if (dist[nv] != -1) continue;

      dist[nv] = dist[v] + 1;
      que.push(nv);
    }
  }
  
  cout << "Yes" << endl;
  for (int i = 1; i < N; i++) {
    for (auto e: G[i]) {
      if (dist[e] == dist[i]-1) {
        cout << e+1 << endl;
        break;
      }
    }
  }
  
}

Measured memory_bytes: 13416
S = int(input())
dp = (S+1)*[0]

for n in range(S+1):
  if 0<=n<=2:
    dp[n] = 0
  elif 3<=n<=5:
    dp[n] = 1
  else:
    dp[n] = (dp[n-3]+dp[n-1])%(10**9+7)

print(dp[S])

Measured memory_bytes: 9008
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>

#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>

#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

// type
#include <cstdint>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    int A, B;
    cin >> A >> B;
    cout << max(0LL, A - 2 * B) << endl;
    return 0;
}

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

using ll = long long;
const ll amari = 1e9+7;
#define ben(a) a.begin(),a.end()
#define pb(a,b) a.push_back(b)

int main(){
	int n,y;
	cin >> n >> y;
	int ok = 1;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			int k = n - i - j;
			if(10000 * i + 5000 * j + 1000 * k == y && i + j + k == n && k >= 0){
				cout << i << " " << j << " " << k << endl;
				ok = 0;
				break;
			}
		}
		if(!ok)break;
	}
	if(ok)cout << -1 << " " << -1 << " " << -1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <functional>
#include <map>
#include <set>

#define INF 1000000000;
#define MOD 1000000007;
typedef long long ll;
using namespace std;

int main()
{
    int ans = 0;
    string s; cin >> s;
    for (auto a : s) {
        if (a == '+') {
            ans++;
        }
        else if (a == '-') {
            ans--;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
#import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

class minus2:
    def __init__(self, arr):
        self.arr = deque(arr)

    def __add__(self, other):
        d = max(len(self), len(other))
        ret = deque([0] * d)
        #print(ret)
        for i in range(1, d+1):
            #print(ret)
            if len(self) >= i:
                ret[-i] += self[-i]
            if len(other) >= i:
                ret[-i] += other[-i]
            if ret[-i] > 1:
                while len(ret) < i+2:
                    ret.appendleft(0)

                delta = ret[-i] // 2
                ret[-i] -= delta * 2
                ret[-i-1] += delta
                ret[-i-2] += delta
            if len(ret) > 1 and ret[0] > 0 and ret[1] > 1:
                delta = max(ret[0], ret[1] // 2)
                ret[0] -= delta
                ret[1] -= delta * 2
                while not ret[0] and len(ret) > 1:
                    ret.popleft()
        '''k = d+1
        while len(ret) >= k:
            print(ret)
            if ret[-k] > 1:
                while len(ret) < k + 2:
                    ret.appendleft(0)
                delta = ret[-k] // 2
                ret[-k] -= delta * 2
                ret[-k - 1] += delta
                ret[-k - 2] += delta
            k += 1'''
        return minus2(ret)

    def __getitem__(self, idx):
        return self.arr[idx]

    def __setitem__(self, i, val):
        self.arr[i] = val

    def __len__(self):
        return len(self.arr)

    def __str__(self):
        return str(self.arr)

def get_val(k, minus = False):
    if minus:
        if k % 2:
            tmp = [0] * (k+1)
            tmp[0] = 1
            return minus2(tmp)
        else:
            tmp = [0] * (k+2)
            tmp[0] = 1
            tmp[1] = 1
            return minus2(tmp)
    else:
        if k % 2:
            tmp = [0] * (k+2)
            tmp[0] = 1
            tmp[1] = 1
            return minus2(tmp)
        else:
            tmp = [0] * (k+1)
            tmp[0] = 1
            return minus2(tmp)

def run():
    N = intread()
    minus = False
    if N < 0:
        minus = True
        N *= -1
    L = N.bit_length()
    ans = minus2([0])
    for k in range(L):
        #print(k)
        #print(ans)
        if (N >> k) & 1:
            #print(k, get_val(k, minus))
            ans += minus2(get_val(k, minus))

    for v in ans:
        print(v, end='')


if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()


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

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

    vector<int> a(M);
    for (int i = 0; i < M; i++) {
        cin >> a[i];
    }

    int div = 1000000007;
    vector<ll> dp(N, 0);

    if (find(a.begin(), a.end(), 1) == a.end()) {
        dp[0] = 1;
    }
    if (find(a.begin(), a.end(), 2) == a.end()) {
        dp[1] = dp[0] + 1;
    }

    for (int i = 2; i < N; i++) {
        if (find(a.begin(), a.end(), i + 1) == a.end()) {
            dp[i] = (dp[i - 1] % div) + (dp[i - 2] % div);
            dp[i] = dp[i] % div;
        }
    }

    cout << dp[N - 1] << endl;

    return 0;
}


Measured memory_bytes: 4312
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second 
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define rep(i,a,b) for( ll i = a ; i < b ; i+=1 )
#define pp pair<ll,ll> 
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t = 1;
const ll inf=hell, N=100005 ;
vector<ll> dist1(N,0), dist2(N,0), adj[N] ;
void solve() 
{
	ll n, x, y, u, v;
	cin>>n>>u>>v;
	rep(i,1,n){
		cin>>x>>y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	vector<ll> vis(N,0);
	queue<ll> q;
	vis[u]=1;
	dist1[u]=0;
	q.push(u);
	while(!q.empty()){
		ll tmp=q.front();
		q.pop();
		for(auto i: adj[tmp]){
			if(vis[i]==0){
				vis[i]=1;
				q.push(i);
				dist1[i]=dist1[tmp]+1;
			}
		}
	}
	q.push(v);
	rep(i,0,N)vis[i]=0;
	vis[v]=1;
	dist2[v]=0;
	while(!q.empty()){
		ll tmp=q.front();
		q.pop();
		for(auto i: adj[tmp]){
			if(vis[i]==0){
				vis[i]=1;
				q.push(i);
				dist2[i]=dist2[tmp]+1;
			}
		}
	}
	ll res=0;
	rep(i,1,n+1){
		//cout << dist1[i] << " " << dist2[i] << "\n" ; 
		if(dist1[i]<dist2[i])
			res=max(res,dist2[i]-1);
	}
	cout<<res<<"\n";
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //cin >> t ;
    while(t--){
        solve();
    }
    return 0 ;
}


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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

int main() {
  int ans = 0;
  int n;
  cin >> n;
  rep(i, n) {
    int l, r;
    cin >> l >> r;
    ans += r - l + 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a,b,c,d;
  cin>>a>>b;
  c=b-a+1;
  for(int i=0;i<a-1;i++){
    cout<<c<<" ";
    c++;
  }
  cout<<b<<" ";
  for(int i=0;i<a-1;i++){
    b+=1;
    cout<<b;
    if(i!=a-1){
      cout<<" ";
    }
  }
  cout<<"\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

long long int mypow(long long int a, long long int b, long long int mod) {
	if (b == 0) return 1 % mod;
	if (b == 1) return a % mod;
	long long int res = mypow(a, b / 2, mod);
	res = res * res % mod;
	if (b % 2 == 1) res = res * a % mod;
	return res;
}

int main() {
    int n;
    cin >> n;
    string x;
    cin >> x;
    int index = -1;
    for (int i = 0; i < n; i++) {
    	if (x[i] == '1') {
    		if (index == -1) {
    			index = i;
    		} else {
    			index = -1;
    			break;
    		}
    	}
    }
    int one = 0;
    for (int i = 0; i < n; i++) {
    	one += x[i] - '0';
    }

    int add_c = 0, minus_c = 0;
    for (int i = 0; i < n; i++) {
    	add_c = add_c * 2 + x[i] - '0';
    	add_c %= one + 1;
    }
    for (int i = 0; i < n && one - 1 > 0; i++) {
    	minus_c = minus_c * 2 + x[i] - '0';
    	minus_c %= one - 1;
    }
    for (int i = 0; i < n; i++) {
    	x[i] = '1' - x[i] + '0';
    	if (index == i) {
    		cout << 0 << endl;
    		x[i] = '1' - x[i] + '0';
    		continue;
    	}
    	int res = 1;
    	int c = 0;
    	if (x[i] == '0')
    		c = ((minus_c - mypow(2, n - i - 1, one - 1)) % (one - 1) + one - 1) % (one - 1);
    	else
    		c = ((add_c + mypow(2, n - i - 1, one + 1)) % (one + 1) + one + 1) % (one + 1);
    	while (c > 0) {
    		res++;
    		int next = c;
    		int bit = 0;
    		while (next > 0) {
    			bit += next % 2;
    			next /= 2;
    		}
    		c %= bit;
    	}
    	cout << res << endl;
    	x[i] = '1' - x[i] + '0';
    }
}


Measured memory_bytes: 3744
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		char [] s = sc.next().toCharArray();
		char bw = s[0];
		int count = 0;
		
		for(int i = 0; i < s.length; i++){
		if(bw != s[i]){ bw = s[i]; count++; }	
		}
		
		System.out.println(count);
	}}

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

int main() {
    cin >> s;
    int a = 0;
    int b = 0;
    for(int i = 0; i < s.length(); ++i) {
        if(s.at(i) == 'A') a++;
        else b++;
    }

    if(a == 0 || b == 0) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

INF = 10**18

N, M, P = map(int, input().split())
G = []
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = INF
            if to == N-1:
                print(-1)
                exit()
if D[N-1] < 0:
    print(0)
else:
    print(D[N-1])


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    int c=0;
    cin>>a>>b;
    rep(i,2){
      if(a>b)c+=a--;
      else c+=b--;
    }
    cout<<c<<endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

int a[200005];
int ans[200005];

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

    int n;
    cin>>n;
    for(int i=2; i<=n; i++)cin>>a[i];
    for(int i=2; i<=n; i++)ans[a[i]]++;
    for(int i=1; i<=n; i++)cout<<ans[i]<<" ";

    cout<<"\n";

    return 0;
}

Measured memory_bytes: 5164
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>
using namespace std;

//	データセットの終わりを処理したら0,
//	それ以外なら1を返す関数
//	問題を解く部分
int solve();

int main() 
{
	while(solve()){}
	return 0;
}

int solve() 
{
	int n;
	cin >> n;
	int cnt[2] = {};
	
	bool b = true;
	
	for(int i = 0; i < n; i++) 
	{
		string str;
		cin >> str;
		
		if( str == "A" ) 
		{
			cnt[0] ++;
		}
		else
		{
			cnt[1] ++;
		}
		
		if(cnt[1] > cnt[0])
		{
			b = false;
		}
	}
	
	if( b && cnt[1] == cnt[0] ) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
	
	
	return 0;
}


Measured memory_bytes: 3168
#include<bits/stdc++.h>
#define lld long long
#define pb push_back
#define mk make_pair
#define MAX 1e9+7
#define lim 1e5
using namespace std;

int main()
{
	lld n,w;

	cin>>n>>w;

	std::vector<lld> weight(n+2);
	std::vector<lld> value(n+2);

	for(lld i=1;i<=n;i++)
	{
		cin>>weight[i];
		cin>>value[i];
	}


	lld dp[n+1][w+1];

	memset(dp,0,sizeof(dp));

	for(lld i=1;i<=n;i++)
	{
		for(lld j=1;j<=w;j++)
		{
			
			if(j-weight[i]>=0)
				dp[i][j] = max(  dp[i-1][j-weight[i]] + value[i] , dp[i-1][j] );
			
			else
				dp[i][j] = dp[i-1][j];
		}
	}

	cout<<dp[n][w]<<endl;
}

Measured memory_bytes: 79104
#include<iostream>
using namespace std;
int main()
{
  int N,A,B,C,X;
  while(cin>>N>>A>>B>>C>>X&&N){
    int Y[N];
    for(int i = 0; i < N; ++i){
      cin >> Y[i];
    }
    int x=X;
    int frame=0;
    int now_reel=0;
    while(true){
      if(x==Y[now_reel])++now_reel;
      if(now_reel==N)break;
      ++frame;
      if(frame>10000){
	frame=-1;
	break;
      }
      x=(A*x+B)%C;
    }
    cout<<frame<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
/*****Here we go again!******/

#include<bits/stdc++.h>
using namespace std;

#define pi 3.1415926535
#define endl "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ll long long
#define llu unsigned long long
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define tc int test_case; cin >> test_case; while(test_case--)
#define f(i,a,n) for(int i = a ; i < n ; i++)
#define rf(i,n,a) for(int i = n-1 ; i >= a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define get(a,n) f(i,0,n) cin >> a[i];
#define show(a,n) f(i,0,n) cout << a[i] << " "; cout << endl;
#define fast ios:: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define trace(x) cerr << '>' << #x << ':' << (x) << "\n"
#define trace2(x,y) cerr<< '>' << #x << ':' << (x) << " | " << #y << ':' << (y) << "\n"
#define trace3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define trace4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"

typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;
typedef map<int,int> mii;
typedef map<ll,ll> mll;

const int inf = 1e9;
const ll inf64 = 1e18;
const int mod = inf + 7;
const int N = 1e5 + 10;

int main()
{
    fast;
    int n, w, maxv = 0;
    cin >> n >> w;
    vi wt(n), val(n);
    f(i,0,n)
    {
        cin >> wt[i] >> val[i];
        maxv += val[i];
    }
    ll dp[N];

    f(i,1,maxv+1)
        dp[i] = inf64;
    dp[0] = 0;

    f(item,0,n)
    {
        int w = wt[item], v = val[item];
        rf(i,maxv+1,v)
            dp[i] = min(dp[i], dp[i-v] + w);
    }
    rf(i,maxv+1,0)
    {
        if(dp[i] <= w)
        {
            cout << i;
            break;
        }
    }
}


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

using namespace std;

int main ()
{

    int a,b;
    while(cin>>a>>b)
    {
        if(a<b)
            cout<<"a < b"<<endl;
        else if(a>b)
            cout<<"a > b"<<endl;
        else
            cout<<"a == b"<<endl;
    }
}



Measured memory_bytes: 3104
'use strict';

const CORRECT_ANSWER = 'AC';
const WRONG_ANSWER = 'WA';

const FIRST_CHARACTER_REQUIREMENT = 'A';

const SINGLE_OCCURRENCE_START_INDEX = 2;

const isFirstCharacterValid = input => input.charAt(0) === FIRST_CHARACTER_REQUIREMENT;
const isSingleOccurenceCharacterValid = input => {
    const cMatch = input.substring(SINGLE_OCCURRENCE_START_INDEX, input.length-1).match(/C/g);

    return cMatch !== null && cMatch.length === 1;
};
const areRemainingCharactersLowercase = input => {
    const clearedAC = input.replace(/[AC]/g, "");

    return clearedAC.toLowerCase() === clearedAC;
}

const process = input => isFirstCharacterValid(input) && isSingleOccurenceCharacterValid(input) && areRemainingCharactersLowercase(input) ? CORRECT_ANSWER: WRONG_ANSWER;

console.log(process(require("fs").readFileSync("/dev/stdin", "utf8").trim()));

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e18)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

struct Edge {
    int to, a, b;
    Edge(int to, int a, int b) : to(to), a(a), b(b) {}
};

struct Data {
    int v, s;
    ll x;
    Data(int v, int s, ll x) : v(v), s(s), x(x) {}
    bool operator<(const Data& a) const {
        return (x > a.x);
    }
};

const int a_max = 50;

int main(){
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<Edge>> g(n);
    rep(i, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        --u; --v;
        g[u].emplace_back(v, a, b);
        g[v].emplace_back(u, a, b);
    }
    vi c(n), d(n);
    rep(i, n) {
        cin >> c[i] >> d[i];
    }
    const int sm = a_max * n;
    s = min(s, sm);
    vector<vll> dp(n, vll(sm+5, INF));
    priority_queue<Data> q;
    auto push = [&] (int v, int s, ll x) {
        if (s < 0) return;
        if (dp[v][s] <= x) return;
        dp[v][s] = x;
        q.emplace(v, s, x);
    };
    push(0, s, 0);
    while (!q.empty()) {
        Data p = q.top(); q.pop();
        int v = p.v, s = p.s;
        ll x = p.x;
        if (dp[v][s] != x) continue;
        {
            int ns = min(s+c[v], sm);
            push(v, ns, x+d[v]);
        }
        for (Edge e : g[v]) {
            push(e.to, s-e.a, x+e.b);
        }
    }
    rep1(i, n-1) {
        ll ans = INF;
        for (ll j : dp[i]) {
            ans = min(ans, j);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 6172
from collections import deque
H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = [list(map(str, input())) for _ in range(H)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] == '.':
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[DH-1][DW-1])

Measured memory_bytes: 241820
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define RFOR(i,m,n) for(int i=m;i>=n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265

int n;
int a[1000000];

int main(){
  cin>>n;

  rep(i,n){
    int b;
    cin>>b;
    a[b] = i+1;
  }

  int ans = n-1;
  int t = 1;
  FOR(i,2,n+1){
    int j=i;
    while(a[j-1]<a[j]) j++;
    ans = min(ans,n-(j-i+1));
    i=j;
  }

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main() {
	string s;
	cin>>s;
	ll d[2];
	clr(d,0);
	rep(i,0,s.sz){
		ll a = i%2;
		if(a!=s[i]-'0')d[0]++;
	}
	rep(i,0,s.sz){
		ll a = (i+1)%2;
		if(a!=s[i]-'0')d[1]++;
	}
	cout << min(d[0],d[1]) << endl;
	return 0;
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

typedef long long ll;

int main(){
  int N, K;
  cin >> N >> K;
  
  cout << N-K+1 << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

print(-ans)


Measured memory_bytes: 34152
#include<stdio.h>
short H, W, i, j;
char A[100][101];
int main(){
	scanf("%hd %hd\n", &H, &W);
	for(i=-2; i<W; ++i){
		putchar('#');
	}
	putchar(10);
	for(j=0; j<H; j++){
		putchar('#');
		for(i=0; i<W; ++i){
			putchar(getchar());
		}
		putchar('#');
		putchar(getchar());
	}
	for(i=-2; i<W; ++i){
		putchar('#');
	}
	putchar(10);
}

Measured memory_bytes: 128
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(void){
    int N;
    cin >> N;
    map<string, int> dict;
    int max = 0;
    for (string x; N--; dict[x]++) {
        cin >> x;
        dict[x]++;
        max = std::max(max, dict[x]);
        //cout << "入力文字列: " << x << ", 出現回数: " << dict[x] + 1 << "回" << endl;
    }
    max++;
    //cout << max << endl;
    priority_queue<string, vector<string>, greater<string>> que;
    for (auto x : dict) {
        //cout << x.second << endl;
        
        if (x.second == max)
            //cout << x.first << endl;
            que.push(x.first);
        //std::cout << x.first << " " << x.second << "\n";
    }
    
    while (!que.empty()) {
      std::cout << que.top() << std::endl;
      que.pop();
    }
}


Measured memory_bytes: 26868
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int main(){
    int n,k,x;
    int i,j;
    scanf("%d %d",&n,&k);
    int a[n+1];
    int d;

    for(i=0;i<n;i++){
        a[i]=0;
    }

    for(i=0;i<k;i++){
        d = 0;
        scanf("%d",&d);
        for(j=0;j<d;j++){
            scanf("%d",&x);
            a[x-1] += 1;
            x = 0;
        }
    }
    int c =0;
    for(i=0;i<n;i++){
        if(a[i]==0){
            c += 1;
        }
    }

    printf("%d",c);

    return 0;
}


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

int main() {
	int w, h, x, y, r;

	cin >> w >> h >> x >> y >> r;

	if ( x >= r && x <= (w - r) && y >= r && y <= (h - r) ){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}


	return 0;
}


Measured memory_bytes: 3100
n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort()
a_max = a_ls[-1]
times_ls = [0] * (a_max + 1)
divisible_ls = [0] * (a_max + 1)
for i in range(n):
    base = a_ls[i]
    times_ls[base] += 1
    times = 2
    while base*times <= a_max:
        divisible_ls[base*times] = 1
        times += 1
ans = 0
for i in range(1,a_max+1):
    if times_ls[i] == 1 and divisible_ls[i] == 0:
        ans += 1
print(ans)

    

Measured memory_bytes: 113332
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
const int N=1005;
char s[N];int val[N],n;
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	fp(i,1,n)++val[s[i]];
	if((val['W']!=0)^(val['E']!=0))return puts("No"),0;
	if((val['S']!=0)^(val['N']!=0))return puts("No"),0;
	return puts("Yes"),0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#include<cstdio>

using namespace std;
using P = pair<int, int>;

const int INF = 200000000;
const int NMAX = 200002;

P S, G;
int N;
vector<P> f;
int dp[NMAX];

int main(){
    cin >> S.first >> S.second >> G.first >> G.second;
    int xmin = min(S.first, G.first);
    int xmax = max(S.first, G.first);
    int ymin = min(S.second, G.second);
    int ymax = max(S.second, G.second);

    if (S.first != xmin) {
        P temp = S;
        S = G;
        G = temp;
    }
    //cout << S.first << ", " << S.second << " " << G.first << ", " << G.second << endl;

    cin >> N;
    bool rev = S.second >= G.second;
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        if (x >= xmin && x <= xmax && y >= ymin && y <= ymax) {
            if (rev) y = ymax - y; else y = y - ymin;
            f.push_back(P(x, y));
            //cout << x << ',' << y << endl;
        }
    }
    
    double ans = (xmax - xmin + ymax - ymin) * 100.;

    if (ymin == ymax || xmin == xmax) {
        ans += f.size() * (10 * M_PI - 20);
    } else {
        sort(f.begin(), f.end());

        for (int i = 0; i < NMAX; ++i) {
            dp[i] = INF;
        }

        for (P fi : f) {
            int y = fi.second;
            //cout << y << endl;
            *lower_bound(dp, dp + NMAX, y) = y;
        }
        int fs = lower_bound(dp, dp + NMAX, INF) - dp;
        if (fs < min(xmax - xmin, ymax - ymin) + 1) {
            ans -= fs * (20 - 5 * M_PI);
        } else {
            //cout << "ss" << endl;
            ans += - (fs - 1) * (20 - 5 * M_PI) + (10 * M_PI - 20);
        }
    }
    printf("%.18lf\n", ans);
}

Measured memory_bytes: 2672
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
S = [readline().decode().rstrip() for _ in range(H)]
INF = 10**30
data = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0 
    for j in range(W):
        if S[i][j] == '1':
            data[i][j] += 1

ans_cnt = INF   
for bit_H in range(1 << (H-1)):
    cnt = 0
    ans = []
    new_data = []
    for i in range(H-1):
        if (bit_H >> i) & 1:
            ans.append(i)
    ans.append(H-1)
    tmp = [0]*W
    for i in range(H):
        for j in range(W):
            tmp[j] += data[i][j]
        if i in ans:
            new_data.append(tmp)
            tmp = [0]*W
    group = len(new_data)
    cnt += group-1
    white = [0] * group
    flag = True
    for i in range(W):
        diff = [0] * group
        for j in range(group):
            diff[j] += new_data[j][i]
            white[j] += new_data[j][i]
        max_diff = max(diff)
        if max_diff > K:
            flag = False
            break
        max_white = max(white)
        if max_white > K:
            cnt +=1
            white = diff[:]
    if flag:
        ans_cnt = min(ans_cnt,cnt)
print(ans_cnt)
    


Measured memory_bytes: 75616
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
 
using namespace std;



int MOD=1000000007;
int main(void){
	int N,ans=0;
	cin >> N;
	int A[N+10],B[N+10],C[N+10];
	for(int i=0; i<N; i++) cin >> A[i];
	for(int i=0; i<N; i++) cin >> B[i];
	for(int i=0; i<N-1; i++) cin >> C[i];
	for(int i=0; i<N; i++){
		if(i!=0 && A[i-1]+1==A[i]){
			ans+=C[A[i-1]-1];
		}
		ans+=B[A[i]-1];

	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<(int)(n);i++)
#define N 200010


int main() {
	long long a[N];
	f(i, N)a[i] = 0;
	int n, k;
	long long x, y, z;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%d", &n);
	s = 0;
	f(i, n) {
		scanf("%lld", &a[i]);
		s += a[i];
	}
	x = 0;
	ans = s;
		f(i, n) {
		x += a[i];
		y = max(x, s - x);
		ans = min(ans, (2 * y - s));
	}
	printf("%lld\n", ans);


	return 0;
}

Measured memory_bytes: 1664
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define i64 long long int
#define ran 101101

int n, W;
i64 dp[ran];

void upd(i64 &a, i64 b) {
	if (a==-1 || a>b) a = b;
}

int main() {
	scanf("%d%d", &n, &W);
	memset(dp, -1, sizeof dp);
	dp[0] = 0;
	for(int i=0;i<n;i++) {
		int w, v;
		scanf("%d%d", &w, &v);
		for(int j=n*1000-v; j>=0; j--)
			if (dp[j]>=0)
				upd(dp[j+v], dp[j]+w);
	}
	i64 ans = 0;
	for(int i=n*1000;i>=0;i--)
		if (dp[i]>=0 && dp[i]<=W) {
			printf("%d\n", i);
			break;
		}
	
	return 0;
}

Measured memory_bytes: 896