akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline


class Unionfind():  # Unionfind
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):  # グループの根
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # グループの併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  # グループのサイズ
        return - self.parents[self.find(x)]

    def same(self, x, y):  # 同じグループか否か
        return self.find(x) == self.find(y)


# 解説AC
n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

uf = Unionfind(n)
frnd = [0] * n
for a, b in ab:
    uf.union(a - 1, b - 1)
    frnd[a - 1] += 1
    frnd[b - 1] += 1

brck = [0] * n
for c, d in cd:
    if uf.same(c - 1, d - 1):
        brck[c - 1] += 1
        brck[d - 1] += 1

ans = []
for i in range(n):
    ans.append(uf.size(i) - frnd[i] - brck[i] - 1)
print(*ans)


Measured memory_bytes: 55716
#include <iostream>

using namespace std;

int main(){
    long long m = 1000000000;
    long long S; cin >> S;
    if(S == m * m){
        cout << "0 0 0 " << m << " " << m << " " << m << endl;
    } else if(S <= m){
        cout << "0 0 0 " << S << " 1 " << S << endl;
    } else {
        cout << "1 0 0 " << m << " " << 1+S/m << " " << S%m << endl;
    }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        long h = in.nextLong();
        long w = in.nextLong();
        if(h==1 || w==1) {
            System.out.print(1);
            System.exit(0);
        }
        long x = (long) Math.ceil((double)w/2);
//        System.out.println(x);
        long y;
        if(w%2==0) y = x;
        else y = x - 1;
        long result;
        if(h%2==0) {
            result = (x+y)*h/2;
        }else {
            result = (x+y)*(h-1)/2+x;
        }
        System.out.print(result);

    }

}


Measured memory_bytes: 23124
s=int(input())
l=0
r=1000000000
while(r-l>1):
    c=(r+l)//2
    if c*c>s:
        r=c
    else:
        l=c
res=r*r-s
for i in range(1,100000):
    if res%i==0:
        if res//i<=1000000000:
            print(0,0,r,i,res//i,r)
            break

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

bool search(int a[],int b,int key){
	int i=0;
	a[b]=key;
	while(a[i]!=key){
		i++;
		if(i==b)
		return false;
	}
	return true;
	}
main(){
	int n,q,c,i,key;
	int s[100000];
	c=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%d",&s[i]);
	scanf("%d",&q);
	for(i=0;i<q;i++){
	scanf("%d",&key);
		if(search(s,n,key))
		c++;
	}
	
	printf("%d\n",c);
	return 0;
}



Measured memory_bytes: 3208
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define ll long long
#define P pair<int, int>
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------

void solve(){
}
int main(){
    string s;
    cin >> s;
    int q;
    cin >> q;
    int n = q;
    int ck = 0;//反転の回数を測る
    string before = "";
    string after = "";
    vector<vector<int> >qn(n, vector<int>(2));
    vector<char>sn(n);
    for(int i = 0; i < n; i++){
        cin >> qn.at(i).at(0);
        if(qn.at(i).at(0) == 2){
            cin >> qn.at(i).at(1) >> sn.at(i);
        }
    }
    for(int i = 0; i < n; i++){
        if(qn.at(i).at(0) == 1){
            ck++;//1回反転する
        }
        else if(qn.at(i).at(1) == 2){
            if(ck % 2 == 0){//反転していない時
                after += sn.at(i);//末尾に追加
            }
            else{
                before += sn.at(i);//末尾はもともと先頭側だった方
            }
        }
        else{
            if(ck % 2 == 0){//反転していない時
                before += sn.at(i);//先頭に追加
            }
            else{
                after += sn.at(i);//先頭はもともと末尾だった方
            }
        }
    }
    if(ck % 2 == 0){
        reverse(before.begin(), before.end());
        cout << before << s << after << endl;
    }
    else{
        reverse(s.begin(), s.end());
        reverse(after.begin(), after.end());
        cout << after << s << before << endl;
    }
    solve();
    return 0;
}



Measured memory_bytes: 12160
n,m=map(int,input().split())
a=list(map(int,input().split()))
t=sum(a)/(4*m)
count=0
for i in a:
    if(i>=t):
        count+=1
        if(count>=m):
            print('Yes')
            exit()
        else:
            continue
    else:
        continue
print('No')

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
int main(void){
    int N,D,i,sum=0,x,y;
    double a,b;
    scanf("%d %d",&N,&D);
    for(i=0;i<N;i++){
        scanf("%d %d",&x,&y);
        a=pow(x,2.0);
        b=pow(y,2.0);
        b=sqrt(a+b);
        if(b<=D){
            sum++;
        }
    }
    printf("%d",sum);
    return 0;
}

Measured memory_bytes: 2120
public class Main {

  private static void solve() {
    long x = nl();
    long y = nl();
    if (x % y == 0) {
      System.out.println(-1);
    } else {
      System.out.println(x);
    }
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = System.getProperty("debug");
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 21460
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

#define fi first
#define se second
#define x second
#define y first

typedef pair<int,int> pii;

vector<string> in;
int H, W, N;

int visited[1024][1024] = {0};

int search_length(char s, char g) {
	fill(visited[0], visited[0] + 1024*1024, 0);
	queue<pair<pii, int> > que;
	int vx[] = {1, -1, 0, 0};
	int vy[] = {0, 0, 1, -1};
	for(int i = 0; i < in.size(); i++) {
		for(int j = 0; j < in[0].size(); j++) {
			if(in[i][j] == s) {
				que.push(pair<pii, int>(pii(i, j), 0));
				j = in[i].size();
				i = in.size();
			}
		}
	}
	while(!que.empty()) {
		pair<pair<int,int>, int> tmp;
		tmp = que.front(); que.pop();
		for(int i = 0; i < 4; i++) {
			int x_, y_;
			x_ = tmp.fi.x + vx[i]; y_ = tmp.fi.y + vy[i];
			if(!(x_ < 0 || (int)in[0].size() <= x_ || y_ < 0 || (int)in.size() <= y_)) {
				if(in[y_][x_] == g) {
					return tmp.se + 1;
				}
				if(!visited[y_][x_] && in[y_][x_] != 'X') {
					visited[y_][x_] = 1;
					que.push(pair<pii,int>(pii(y_, x_), tmp.se + 1));
				}
			}
		}
	}
	return -1;
}

int main() {
	cin >> H >> W >> N;
	int ret = 0;
	for(int i = 0; i < H; i++) {
		string tmp;
		cin >> tmp;
		in.push_back(tmp);
	}

	for(int i = 0; i < N; i++) {
		char s, g;
		s = i + '0'; g = i + 1 + '0';
		if(i == 0)
			s = 'S';
		ret += search_length(s, g);
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 6220
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define watch(x) cout << (#x) << " is: " << (x) << endl
#define vw(v)                        \
    cout << endl                     \
         << endl                     \
         << (#v) << " is: " << endl; \
    for (ll B : (v))                 \
    {                                \
        cout << B << " ";            \
    }                                \
    cout << endl
#define check(x) cout << "here " << (x) << "?" << endl
#define rep(i, a, b) for (long long i = (a); i < (b); i++)
#define per(i, a) for (long long i = (a - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rv(x) (x).rbegin(), (x).rend()
#define pb push_back
typedef long long ll;
ll const MAX = 2147483647, REALMAX = 9223372036854775806;
ll const N = 1e6;

int main()
{
    FAST_IO
    ll n;
    cin >> n;
    vector<ll> v, v1(n), v2(n);
    rep(i, 1, n + 1)
        v.pb(i);
    rep(i, 0, n)
            cin >> v1[i];
    rep(i, 0, n)
            cin >> v2[i];
    ll lst = -1;
    vector<vector<ll>> ans;
        ans.pb(v);
    while (next_permutation(v.begin(), v.end()))
        ans.pb(v);
    if (v1 == v2)
        return cout << 0 , 0;
    rep(i, 0, ans.size())
    {
        if (ans[i] == v1 || ans[i] == v2)
        {
            if (lst != -1)
                return cout << abs(i - lst) , 0;
            else
                lst = i;
        }
    }
}

Measured memory_bytes: 4408
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int ans;

    if(N%2 == 0){
      ans = N;
    }else{
      ans = 2*N;
    }
    
    System.out.println(ans);
  }
}


Measured memory_bytes: 21972
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100025;
const int inf=0x3f3f3f3f;
ll dp[maxn],arr[maxn];
int main()
{
    int n,k;
	cin>>n>>k;
    for(int i=1;i<=n;++i)
	cin>>arr[i];
    for(int i=2;i<=n;++i)
    {
    	dp[i]=inf;
        for(int j = 1;j<=k;++j)
        {
            if(i-j<1)
			break;
            dp[i]=min(dp[i],dp[i-j]+abs(arr[i]-arr[i-j]));
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 5184
s=sorted(map(int,input().split()))
ans=0
while s[0]+2<=s[2]:
    s[0]+=2
    ans+=1
while s[1]+2<=s[2]:
    s[1]+=2
    ans+=1
    
s=sorted(s)
if s[0]==s[2]:
    print(ans)
elif s[0]==s[1]:
    print(ans+1)
else:
    print(ans+2)

Measured memory_bytes: 9148
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Array;
using static AtCoderSolve.Tool;

namespace AtCoderSolve
{
    class Solve
    {
        const int mod = 1000000007;
        const int INF = int.MaxValue / 2;
        const long SINF = long.MaxValue / 2;

        static void Main(string[] args)
        {
            //var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            //Console.SetOut(sw);
            var cin = new Scanner();
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            int[] t = new int[26];
            Initialize(ref t, 0);
            for(var i = 0; i < N; i++)
            {
                t[S[i] - 'a']++;
            }

            long ans = 1;
            for(var i = 0; i < 26; i++)
            {
                ans = (ans * (1 + t[i])) % mod;
            }
            Console.WriteLine(ans - 1);


            //Console.Out.Flush();
        }


    }

    public class Scanner
    {
        public int[] SplitReader()
        {
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return array;
        }
        public long[] SplitReaderL()
        {
            long[] array = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return array;
        }
    }

    public static class Tool
    {
        static public void Initialize<T>(ref T[] array, T initialvalue)
        {
            for(var i = 0; i < array.Length; i++)
            {
                array[i] = initialvalue;
            }
        }
    }

    struct Pair<T> : IComparable<Pair<T>> where T : IComparable<T>
    {
        public T variable;
        public int index;

        public Pair(T val, int i)
        {
            variable = val;
            index = i;
        }

        public int CompareTo(Pair<T> otherPair)
        {
            return variable.CompareTo(otherPair.variable);
        }

        public int CompareIndex(Pair<T> otherPair)
        {
            return index.CompareTo(otherPair.index);
        }
    }



}






Measured memory_bytes: 13116
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    long long int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0 ; i < n ; i++){
        int a ; 
        cin >> a;
        v[i] = a;
    }

    vector<int> ans(n);
    ans[0] = 0;
    ans[1] = abs(v[1] - v[0]);
    for (int i = 2 ; i < n ; i++){
        ans[i] = min(ans[i-1] + abs(v[i-1] - v[i]), ans[i-2] + abs(v[i-2] - v[i]));
    }
    cout << ans[n-1];
    return 0;
}


Measured memory_bytes: 3972
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
def main():
    N, M, K = map(int, readline().split())
    A = [int(i) for i in readline().split()]
    B = [int(i) for i in readline().split()]

    ca = [0]
    cb = [0]
    for i in range(N):
        ca.append(ca[i] + A[i])
    for i in range(M):
        cb.append(cb[i] + B[i])

    ans = 0  
    j = M
    for i in range(N+1):
        if K < ca[i]:
            break
        while cb[j] > K-ca[i]:
            j -= 1
        ans = max(ans, i+j)
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 139492
#include <bits/stdc++.h>
using namespace::std;
#define all(x) (x).begin(),(x).end()
#define int long long


const int N = 2e5 + 1;
vector<int> adj[N];
vector<int> path;
bitset<N> vis;
bitset<N> cycle;

void dfs(int cur) {
        vis[cur] = true;
        path.emplace_back(cur);
        for (const auto next: adj[cur]) {
                if (!vis[next]) {
                        dfs(next);
                } else {
                        cycle[next] = true;
                        return;
                }
        }
}

signed main() { /*[J][O][L][S][K][E][Y]*/
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int n, k; cin >> n >> k;
        for (int i = 1; i <= n; i++) {
                int a; cin >> a;
                adj[i].emplace_back(a);
        }

        dfs(1);
        if (cycle[1]) {
                cout << path[k % path.size()];
                return 0;
        }


        for (int i = 1; i < path.size(); i++) {
                k--;
                if (!k) {
                        cout << path[i];
                        return 0;
                }
                if (cycle[path[i]]) {
                        int sz = path.size() - i;
                        cout << path[k % sz + i];
                        return 0;
                }

        }

        return 0;
}

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

int main() {
	vector <string> s;
	int n,l;
	string ss;
	cin>>n;
	cin>>l;
	while(n--){
		
		cin>>ss;
	
		s.emplace_back(ss);
	}
	
	sort(s.begin(), s.end());
	
	ss="";
	
	for(const string &u:s) ss+=u;
	
	
	cout<<ss;
	
	return 0;
}

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

int main() {
	int a, b;
	cin >> a >> b;
	int ans;
	ans = max(a+b, max(a-b, a*b));
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3580
N,M,X,Y= map(int, input().split())
x_list = [int(e) for e in input().split()]
y_list = [int(e) for e in input().split()]

for i in range(X+1,Y+1):
  if max(x_list) < i and min(y_list) >= i:
    print("No War")
    break
else:
  print("War")

Measured memory_bytes: 3060
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

L = [LIST() for i in range(4)]
ans = sum(min(L[0], L[1]) + min(L[2], L[3]))
print(ans)


Measured memory_bytes: 5400
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var raw = ReadLine().Split().Select(long.Parse).ToArray();
            var N = raw[0];
            var K = raw[1];

            WriteLine(Math.Min(N % K, K - N % K));
        }
    }
}


Measured memory_bytes: 13396
#include <iostream>
using namespace std ;
	
int main(void){	
	
int N,temp;
bool ok=true;
cin >> N;

while(N>0){
	cin >> temp;
	if(temp%2) N--;
	else if(temp%3  && temp%5 ){
			printf("DENIED");
			ok = false;
			break;}
  	else N--;
}
if(ok)
printf("APPROVED");

return 0;
}

Measured memory_bytes: 256
//abc148E
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void) {
  int i;
  long long n=0, tmp=10, mp5=1, cou=0, sum=0;
  //N,tmp:10*5^X,mp5:N=tmpのときの0の個数,cou:X,sum:Nのときの0の個数計測
  scanf(" %lld", &n);

  if(n % 2 == 1) printf("0");//奇数なら0
  else{
    while(tmp < n)
      tmp*=5, mp5=mp5 * 5 + 1, cou++;//10を5倍するごとに10の倍数はX*5+1倍
    for(i=cou; i >= 0; i--){
      if(n >= tmp) sum+=(n / tmp) * mp5, n%=tmp;//a*10*5^Xのときの0の個数を計上、n-a*10*5^X
      mp5=(mp5 - 1) / 5, tmp/=5;//a*10*5^(X-1)のときの0の個数に変更、tmp=a*10*5^X
    }
    printf("%lld", sum);
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iterator>
#include <functional>
#include <numeric>
#include <cmath>
#include <stack>
#include <limits>

using namespace std;

#define ll long long
#define f0(i,n)for(i=0;i<n;i++)
#define f1(i,n)for(i=1;i<=n;i++)
#define fc(i,c,n)for(i=c;i<=n;i++)
#define f0r(i,n)for(i=n-1;i>=0;i--)
#define f1r(i,n)for(i=n;i>0;i--)
#define fcr(i,c,n)for(i=n;i>=c;i--)
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef list<ll> LST;
typedef vector<ll> VEC;
typedef map<ll, ll> MAP;

static int i, j, q;

int main() {
    IO;
    //ifstream cin("In.txt");
    ll n,p,m,ans=0,k;
    string st;
    cin>>n;
    k = sqrtl(n);
    f1(i,k){
        if(n%i==0){
            m = (n/i)-1;
            if(m>i)
                ans+=m;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int INF = 1 << 30;
typedef pair < int , int > Pi;
int n, m, mas[101][101], hoge[4][51][51];

bool isfind( const int& k, const int& y, const int& x, Pi& exitp)
{
  for(int i = 0 ; i < m ; i++ ){
    for(int j = 0 ; j < m ; j++ ){
      if( hoge[k][i][j] == -1) continue;
      if( mas[i + y][j + x] != hoge[k][i][j]) return false;
      if(exitp == Pi(-1,-1)) exitp = Pi(i + y + 1,j + x + 1);
    }
  }
  return true;
}

Pi solve()
{

  for(int i = 0 ; i <= n - m ; i++ ){

    for(int j = 0 ; j <= n - m ; j++ ){
      Pi ret = Pi( INF, INF);
      for(int k = 0 ; k < 4 ; k++ ){
        Pi p = Pi( -1, -1);
        if(isfind( k, i, j, p)){
          ret = min( ret, p);
        }
      }
      if(ret.first != INF) return ret;
    }
  }
  return Pi( INF, -1);
}
int main()
{
  while(cin >> n >> m, n){
    for(int i = 0 ; i < n ; i++ ){
      for(int j = 0 ; j < n ; j++ ){
        cin >> mas[i][j];
      }
    }
    for(int i = 0 ; i < m ; i++ ){
      for(int j = 0 ; j < m ; j++ ){
        cin >> hoge[0][i][j];
      }
    }

    for(int k = 1 ; k < 4 ; k++ ){
      for(int i = 0 ; i < m ; i++ ){
        for(int j = 0 ; j < m ; j++ ){
          hoge[k][j][m - i - 1] = hoge[k - 1][i][j];
        }
      }
    }

    Pi pos = solve();
    if(pos.first == INF) cout << "NA" << endl;
    else cout << pos.second << " " << pos.first << endl;
  }
  return 0;
}

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

const int maxn = 100+5;
const int maxm = 1e5+5;

long long f[maxn][maxm];
int obj[maxn],w[maxn];
int W,n;

int main(){
	cin >> n >> W;

	for (int i = 1; i <= n; i++){
		cin >> w[i];
		cin >> obj[i];
	} 
	
	for (int i = 1; i <= n; i++){
		for (int j = 0; j <= W; j++){
			if (w[i] > j){
				f[i][j] = f[i - 1][j];
			}else{
				
				f[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + obj[i]);
			}
		}
	}
	
	cout << f[n][W] << endl;
	
	return 0;
}

Measured memory_bytes: 79360
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            String S = Console.ReadLine();

            List<String> ansyou = new List<string>();

            String ansyou_i = "";
            String ansyou_j = "";
            String ansyou_k = "";

            int[] syouryaku_i = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
            for (int i = 0; i < N - 2; i++) {
                ansyou_i = S.Substring(i, 1);
                if (syouryaku_i[int.Parse(ansyou_i)] == 0) {
                    syouryaku_i[int.Parse(ansyou_i)] = 1;
                    int[] syouryaku_j = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
                    for (int j = i + 1; j < N - 1; j++) {
                        ansyou_j = S.Substring(j, 1);
                        if (syouryaku_j[int.Parse(ansyou_j)] == 0) {
                            syouryaku_j[int.Parse(ansyou_j)] = 1;
                            int[] syouryaku_k = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
                            for (int k = j + 1; k < N; k++) {
                                ansyou_k = S.Substring(k, 1);
                                if (syouryaku_k[int.Parse(ansyou_k)] == 0) {
                                    syouryaku_k[int.Parse(ansyou_k)] = 1;
                                    StringBuilder S_new = new StringBuilder();
                                    S_new.Append(ansyou_i);
                                    S_new.Append(ansyou_j);
                                    S_new.Append(ansyou_k);
                                    ansyou.Add(S_new.ToString());
                                }
                            }
                        }
                    }
                }

            }

            ansyou = ansyou.Distinct().ToList();

            Console.WriteLine(ansyou.Count);

        }
    }
}


Measured memory_bytes: 17584
#include<iostream>

#define INF 12345678
using namespace std;


int main() {
	int n, m, x;
	int c[12];
	int a[12][12];
	int i, j, k, l;
	
	int knowledge[12] = { 0 };

	int buy_bool[12];

	int expo_n, i_tmp, price_sum, price_min;

	bool archive_flg = true;

	price_min = INF;

	cin >> n >> m >> x;

	for (i = 0; i < n; i++) {
		cin >> c[i];
		for (j = 0; j < m; j++) cin >> a[i][j];
	}
	expo_n = 1;
		for (i = 0; i < n; i++) expo_n *= 2;
	
	for (i = 1; i < expo_n; i++) {
		i_tmp = i;
		for (j = 0; j < n; j++) {
			buy_bool[j] = 0;
			buy_bool[j] = i_tmp % 2;
			i_tmp /= 2;
		}

		for(j = 0; j < m; j++) knowledge[j] = 0;

		price_sum = 0;
		for (j = 0; j < n; j++) {
			if (buy_bool[j] != 0) {
				price_sum += c[j];
				for (k = 0; k < m; k++) knowledge[k] += a[j][k];	
			}
		}

		
		archive_flg = true;
		for (j = 0; j < m; j++) {
			if (knowledge[j] < x) {
				archive_flg = false;
			}
		}
		
		if (archive_flg && price_min > price_sum) {
			price_min = price_sum;
		}
	}

	if(price_min == INF) cout << -1 << endl;
	else cout << price_min << endl;
	return 0;
}


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}


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

  int n; cin >> n;
  string s; cin >> s;
  int cntb = 0, cntw = 0;
  for(int i=0;i<n;++i) {
    cntw += s[i] == '.';
  }

  int ans = INF;
  for(int i=0;i<n;++i) {
    ans = min(ans, cntb + cntw);
    cntb += s[i] == '#';
    cntw -= s[i] == '.';
  }
  ans = min(ans, cntb + cntw);
  cout << ans << endl;
  

}


Measured memory_bytes: 720
// 2020-08-02 21:03:42
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  ll k;
  cin >> k;
  vector<int> mp(k+1, 0);
  if(k % 2 == 0) {
    cout << -1 << '\n';
    return;
  }
  ll cnt = 1, cur = 7;
  while(1) {
    if(cur % k == 0) {
      cout << cnt << '\n';
      return;
    } else if(mp[cur % k] > 0) {
      cout << -1 << '\n';
      return;
    } else {
      mp[cur % k]++;
    }
    cur *= 10;
    cur += 7;
    cur %= k;
    cnt++;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 7128
x, n = map(int, input().split())
try:
  list_P = [int(p) for p in input().split()]
  list_not_P = [x for x in range(102) if not x in list_P]
  list_abs = [abs(x - i) for i in list_not_P]
  Index = list_abs.index(min(list_abs))
  print(list_not_P[Index])
except EOFError:
  print(x)

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

int main() {
	int N;
	cin >> N;
	int p[60];
	for (int i = 0; i < N;++i) {
		cin >> p[i];
	}

	int count = 0;

	for (int i = 0; i < N; i++) {
		if ((i+1)!=p[i]) {
			count += 1;
		}
	}

	if(count<=2){
		cout << "YES" << endl;

	}
	else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e18 + 7, N = 2e5 + 7;

int dp[N][3], a[N];

int take(int i, int j) {
	return (i + 1 + 1) / 2 - j;
}

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	dp[0][0] = a[0], dp[0][1] = 0, dp[0][2] = -INF;
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < 3; j++) {
			dp[i][j] = -INF;
			int want = take(i, j);
			for(int k = 0; k < 3; k++) {
				if(take(i-1, k) == want) dp[i][j] = max(dp[i][j], dp[i-1][k]);
			}
			if(i-2 >= 0) {
				for(int k = 0; k < 3; k++) {
					if(take(i-2, k) + 1 == want) dp[i][j] = max(dp[i][j], dp[i-2][k] + a[i]);
				}
			} else {
				if(want == 1) dp[i][j] = max(dp[i][j], a[i]);
			}
			// cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
		}
	}

	cout << dp[n-1][n & 1] << endl;
}





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

#define ll long long
#define mod 1000000007
#define ffor(i,a,b) for(int i=a;i<b;i++)
#define bfor(i,a,b) for(int i=a-1;i>=b;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mem(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sz(x) (int)x.size()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI 3.14159265358979323846
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define endl '\n'

int main()
{
    

    string s;
    cin>>s;
    if(s[2]==s[3]&&s[4]==s[5]) cout<<"Yes";
    else cout<<"No";
    
    return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1E9 + 9;
const int INF = 1 << 29;

int main() {
  string S;
  cin >> S;
  int n = S.length();
  vector<int> v(n);
  int op = -1;
  rep(i, n) v[i] = int(S.at(i) - '0');
  for (int i = 0; i < (1 << (n - 1)); ++i) {
    int ans = v[0];
    for (int j = 0; j < (n - 1); ++j) {
      if (i & (1 << j)) {
        ans += v[j + 1];
      } else {
        ans -= v[j + 1];
      }
    }
    if (ans == 7) {
      op = i;
      break;
    }
  }
  if (op == -1) {
    cout << "IMPOSSIBLE!" << endl;
    return 0;
  }
  cout << v[0];
  for (int i = 0; i < (n - 1); i++) {
    if (op & (1 << i)) {
      cout << '+';
    } else {
      cout << '-';
    }
    cout << v[i + 1];
  }
  cout << "=7" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits//stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long int ll;
ll x,x2,y2,n,k,sum = 0,pre = 0; string s;
int main() {
	cin >> n; vector<ll> a(n);
	rep(i, n) cin >> a[i];
	rep(i, n) {
		sum += a[i] / 2;
		if (i < n - 1 && a[i] & 1 && a[i + 1] > 0) sum++, a[i + 1]--;
	}cout << sum << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    for(int i = 0; i <= b; i++){
        if(a*i%b==c){cout << "YES" << endl; return 0;}
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
//DP2
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
using namespace std;

int main(){
	int n, k;
	cin >> n >> k;
	vector<long long int> h(n);
	for(int i=0;i<n;i++){
		cin >> h.at(i);
	}
	vector<long long int> cost(n);
	for(int i=0;i<n;i++){
		cost.at(i) = 1e9;
	}
	cost.at(0) = 0;
	cost.at(1) = abs(h.at(1) - h.at(0));
	if(n >= 3){
		for(int i=2;i<k;i++){
			for(int j=0;j<i;j++){
				cost.at(i) = min(cost.at(i),cost.at(j) + abs(h.at(i) - h.at(j)));
			}
		}
	}
	if(n >= k){
		for(int i=k;i<n;i++){
			for(int j=i-k;j<i;j++){
				cost.at(i) = min(cost.at(i),cost.at(j) + abs(h.at(i) - h.at(j)));
			}
		}
	}
	cout << cost.at(n-1) << endl;
	return 0;
}
			

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  int K[N];
  int A[N][M];
  for(int i=0;i<N;i++){
    cin >> K[i];
    for(int j=0;j<K[i];j++){
      cin >> A[i][j];
    }
  }
  int ans = 0;
      for(int j=0;j<K[0];j++){
        int cnt = 0;
        for(int i=1;i<N;i++){
        for(int k=0;k<K[i];k++){
          if(A[0][j] == A[i][k]){
            cnt++;
          }
        }
      }
      if(cnt==N-1){
        ans++;
      }
    }
    if(N==1){
      ans = K[0];
    }
    cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {
    long long T[2], A[2], B[2];
    cin >> T[0] >> T[1] >> A[0] >> A[1] >> B[0] >> B[1];
    
    long long D[2];
    for (int i = 0; i < 2; i++) D[i] = T[i] * (A[i] - B[i]);
    if (D[0] + D[1] == 0) {
        cout << "infinity" << endl;
        return 0;
    } else {
        if (D[0] > 0) {
            D[0] *= -1;
            D[1] *= -1;
        }
        if (D[0] + D[1] < 0) {
            cout << 0 << endl;
        } else {
            long long S = (-1) * D[0] / (D[0] + D[1]);
            long long T = (-1) * D[0] % (D[0] + D[1]);
            cout << (2 * S + (T == 0 ? 0 : 1)) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_temp>
using smaller_queue = priority_queue<Q_temp, vector<Q_temp>, greater<Q_temp>>;

const ll MOD = (ll)(1e9 + 7);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

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

  auto same = [](vector<int> &v1, vector<int> &v2) {
    rep(i, v1.size())
    {
      if (v1[i] != v2[i])
        return false;
    }
    return true;
  };

  int n;
  cin >> n;
  vector<int> p(n), q(n);
  rep(i, n) cin >> p[i];
  rep(i, n) cin >> q[i];
  int p_cnt = 0, q_cnt = 0;
  vector<int> v1(n), v2(n);
  rep(i, n)
  {
    v1[i] = v2[i] = i + 1;
  }
  while (!same(p, v1))
  {
    NP(v1);
    p_cnt++;
  }
  while (!same(q, v2))
  {
    NP(v2);
    q_cnt++;
  }
  cout << abs(p_cnt - q_cnt) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int cnt=1;
int oya[500010];
int ko[2][500010];
int val[500010];

int f(int v,int mode){
    if(mode==0)printf(" %d",val[v]);
    if(ko[0][v])f(ko[0][v],mode);
    if(mode==1)printf(" %d",val[v]);
    if(ko[1][v])f(ko[1][v],mode);
    if(mode==2)printf(" %d",val[v]);
}
void push(int v,int va){
	//初回
	if(cnt==1){
		val[cnt]=va;
		cnt++;
		return;
	}
	if(ko[val[v]<va][v])push(ko[val[v]<va][v],va);
	else{
		ko[val[v]<va][v]=cnt;
		oya[cnt]=v;
		val[cnt]=va;
		cnt++;
	}
}

int main(){
	int q;
	scanf("%d",&q);
	while(q--){
		char s[10];
		scanf("%s",s);
		if(s[0]=='p'){
			f(1,1);
			puts("");
			f(1,0);
			puts("");
		}else{
			int t;
			scanf("%d",&t);
			push(1,t);
		}
	}
}


Measured memory_bytes: 9548
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.TreeMap;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] W = new int[N];
        for (int i=0;i<N;i++){
            W[i] = sc.nextInt();
        }
        int[] cum = new int[N+1];
        for (int i=0;i<N;i++){
            cum[i+1] = cum[i] + W[i];
        }
        int ans = Integer.MAX_VALUE;
        for (int i=0;i<N;i++){
            if (Math.abs(cum[i+1]-(cum[N]-cum[i+1]))<ans){
                ans = Math.abs(cum[i+1]-(cum[N]-cum[i+1]));
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;

int main()
{
    long long int a, b, k;
    cin >> a >> b;

    if ((a+b)%2 == 0) {
        k = (a+b)/2;
        cout << k << endl;;
    }
    else {
        cout << "IMPOSSIBLE" << endl;
    }

    return 0;
}


Measured memory_bytes: 3164
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        var nm = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
        var ans = new long[8];
        var inp = new long[nm[0]][];
        for (int i = 0; i < nm[0]; i++) inp[i] = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
        for (int i = 0; i < 8; i++)
        {
            var score = new List<long>();
            for (int j = 0; j < nm[0]; j++)
            {
                long thisScore = 0;
                for (int k = 0; k < 3; k++)
                {
                    if (((i >> k) & 1) == 1) thisScore += inp[j][k];
                    else thisScore -= inp[j][k];
                }
                score.Add(thisScore);
            }
            score = score.OrderByDescending(L => L).ToList();
            ans[i] = score.Where((x, y) => y < nm[1]).Sum();
        }
        Console.WriteLine(ans.Max());
    }
}

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  a.begin(),a.end()

class CommonIO {
public:
  CommonIO() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
  }
  ~CommonIO() {}

  template <class T>
  void scan(T &v) {
      std::cin >> v;
  }
  template <class T, class... Rest>
  void scan(T &v, Rest&... rest) {
      scan(v);
      scan(rest...);
  }

  template <class T>
  void print(T v) {
    std::cout << v;
  }
  template <class T>
  void print(std::vector<T> &v) {
    if (v.size() == 0) return;
    print(*v.begin());
    for (auto it = ++v.begin(); it != v.end(); ++it) {
        print(' ');
        print(*it);
    }
  }
  template <class T>
  void print(std::vector< std::vector<T> > &grid) {
    if (grid.size() == 0) return;
    print(*grid.begin());
    for (auto it = ++grid.begin(); it != grid.end(); ++it) {
      print('\n');
      print(*it);
    }
  }
  template <class T, class... Rest>
    void print(T v, Rest... rest) {
    print(v);
    print(' ');
    print(rest...);
  }

  template <class T>
    void printl(T v) {
    print(v);
    std::cout << '\n';
  }
  template <class T, class... Rest>
    void printl(T v, Rest... rest) {
    print(v);
    print(' ');
    printl(rest...);
  }
  #define original_output(obj) std::ostream& operator<<(std::ostream& stream, const decltype(obj)& obj)
} io;



int main() {
  vector<string> word;
  string s;
  
  while(getline(cin, s, ' ')) {
    word.push_back(s);
  }

  stack<int> num;
  for (auto &w : word) {
    if (isdigit(w[0])) {
      num.push(atoi(w.c_str()));
    }
    else {
      int r = num.top(); num.pop();
      int l = num.top(); num.pop();
      switch(w[0]) {
        case '+':
          num.push(l+r); break;
        case '-':
          num.push(l-r); break;
        case '*':
          num.push(l*r); break;
      }
    }
  }
  io.printl(num.top());

  return 0;
}



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

using ll = long long;
using P = pair<ll, ll>;

const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

string s;
ll dp[100010][13];

int main(int argc, char **argv)
{
	cin >> s;
	ll N = s.size();

	**dp = 1;

	REP(n, N)
	{
		REP(j, 13)
		{
			if (s[n] == '?')
				REP(k, 10)
				{
					(dp[n+1][(j*10+k)%13] += dp[n][j]) %= MOD;
				}
			else
				(dp[n+1][(j*10+(s[n]-'0'))%13] += dp[n][j]) %= MOD;
		}
	}

	std::cout << dp[N][5] << std::endl;
}


Measured memory_bytes: 10624
#include<stdio.h>
int main(void)
{
	int a,b,c,x,y,w,sum,sum1;
	scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);
	sum=0; sum1=-1;
	if(a+b>c*2){
		if(x<y){
			sum1=y*2*c;
			w=x; y-=x; x=0;
		}
		else{
			sum1=x*2*c;
			w=y; x-=y; y=0;
		}
		sum+=w*2*c;
	}
	sum+=a*x;
	sum+=b*y;
	if(sum1!=-1&&sum>sum1) sum=sum1;
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <map>

int main(void) {

	int n;

	std::cin >> n;

	int min = 100000000;
	for (size_t i = 1; i <= n / 2; i++) {
		int a, b;

		a = i;
		b = n - i;

		int asum = 0, bsum = 0;
		while (a != 0) {
			asum += a % 10;
			a /= 10;
		}
		while (b != 0) {
			bsum += b % 10;
			b /= 10;
		}

		min = std::min(min, asum + bsum);
	}

	std::cout << min << std::endl;

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			cout << v[i][j] << "   ";
		}
		cout << endl;
	}
}


int main(){// 全探索：全列挙 4　パ研杯2019 C - カラオケ　これが解ければ全探索に慣れたと思って良いです。
	ll A, B, C, X, Y;
	cin >> A >> B >> C >> X >> Y;
	
	//ll ans = 100100100100100;
	//1. 全部ABピザ
	ll money1 = 2 * max(X, Y) * C;

	//2.　X，Y少ない方のピザの分を全部ABピザ
	ll money2 = 0;
	if(X > Y){
		money2 += Y * 2 * C;
		money2 += (X-Y) * A;
	}
	else{
		money2 += X * 2 * C;
		money2 += (Y-X) *B;
	}

	//3 ABピザを買わない
	ll money3 = A * X + B * Y;

	cout << min( min(money1, money2), money3) << endl;
}

Measured memory_bytes: 256
import bisect

W, H = map(int, input().split())
P = [int(input()) for _ in range(W)]
Q = [int(input()) for _ in range(H)]

P.sort()
Q.sort()

ans = 0
for p in P:
    ind = bisect.bisect_right(Q, p)
    ans += p * (H - ind + 1)
for q in Q:
    ind = bisect.bisect_left(P, q)
    ans += q * (W - ind + 1)
print(ans)


Measured memory_bytes: 11496
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1000000007
#define maxn 1000000009b
int main()
{
    string S;
    cin >> S;
    string T;
    cin >> T;
    int a;
    a = 0;
    for (int i = 0; i < 3; i++)
    {
        if (S[i] == T[i])
        {
            a++;
        }
    }
    cout << a << endl;
}


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

using namespace std;

#define PROD

int main()
{
    int N, D;

#ifdef PROD
    cin >> N >> D;

    vector<vector<int>> X(N, vector<int>(D));
    for(int ii = 0 ; ii < N ; ii++) {
        for(int ij = 0 ; ij < D ; ij++) {
            cin >> X[ii][ij];
        }
    }
#else
    N = 3;
    D = 2;

    vector<vector<int>> X(N, vector<int>(D));
    X[0][0] = 1;
    X[0][1] = 2;
    X[1][0] = 5;
    X[1][1] = 5;
    X[2][0] = -2;
    X[2][1] = 8;
#endif

    auto ans = 0;

    for(int i = 0 ; i < N - 1 ; i++) {
        for(int j = i + 1; j < N ; j++) {
            int sum = 0;
            for(int k = 0 ; k < D ; k++) {
                auto diff = abs(X[i][k] - X[j][k]);
                sum += diff * diff;
            }

            bool f = false;
            for(int k = 0; k <= sum; k++) {
                if(k * k == sum) {
                    f = true;
                }
            }

            if (f) ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<< #str << " " str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7



int main()
{
	int N, K;
	string s;
	cin >> N >> K >> s;
	vector<int> imos(1, 0);

	bool mode = s[0] == '0';
	int cnt = 0;
	REP(i, N) {
		bool now = s[i] == '0';
		if (mode == now)cnt++;
		else {
			imos.push_back(cnt);
			mode = now;
			cnt = 1;
		}
	}
	imos.push_back(cnt);
	/*
	if (s[0] == '1' && s.back() == '1') {
		if (imos.size() <= 2 * K + 1) {
			cout << N << endl;
			return 0;
		}
	}
	else if (s[0] == '1' || s.back() == '1') {
		if (imos.size() <= 2 * K) {
			cout << N << endl;
			return 0;
		}
	}
	else {
		if (imos.size() <= 2 * K - 1) {
			cout << N << endl;
			return 0;
		}
	}
	*/

	REP(i, imos.size() - 1)imos[i + 1] += imos[i];
	int siz = imos.size() - 1;
	int res = 0;
	bool flag = (s[0] == '1');
	REP(l, imos.size()) {
		int len = (flag ? 2 * K + 1 : 2 * K);
		res = max(res, imos[min(l + len, (ll)siz)] - imos[l]);
		flag = !flag;
	}
	cout << res << endl;
	return 0;
}


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

int main() {
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++){
	    cin>>a[i];
	}
	
	bool dp[k+1];
	
	for(int i=0;i<=k;i++){
	    dp[i]=false;
	}
	
	for(int i=1;i<=k;i++){
	    
	    for(int j=0;j<n;j++){
	        if(i-a[j]<0)
	        break;
	        
	        if(dp[i-a[j]]==false){
	           dp[i]=true;
	           break;
	        }
	    }
	    
	}
	
	if(dp[k]==true)
	cout<<"First";
	else
	cout<<"Second";
	
	return 0;
}

Measured memory_bytes: 384