akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 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;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int N = in.nextInt();
			int K = in.nextInt();
			int[] l = new int[N];
			for(int i = 0; i < l.length; i++) {
				l[i] = in.nextInt();
			}
			Arrays.sort(l);
			int ans = 0;
			for(int i = l.length - 1; i >= l.length - K; i--) {
				ans += l[i]; 
			}
			out.println(ans);
		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public char nextChar() {
			return next().charAt(0);
		}

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

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

	}
}


Measured memory_bytes: 21332
h,w,k=map(int,input().split())

c=[0]*h
for i in range(h):
    c[i]=input()

cnt=0

for rows in range(1<<h):
    for cols in range(1<<w):
        black=0
        for i in range(h):
            if (rows >> i) %2==1:
                continue
            for j in range(w):
                if (cols >> j) %2==1:
                    continue
                black += c[i][j] =="#"
        if black==k:
            cnt+=1

print(cnt)

Measured memory_bytes: 9212
N, M = [int(num) for num in input().split(' ')]

ans = [0 for i in range(N)]
done = [False for i in range(N)]

suc = 0

for j in range(M):
	# p is 0 indexed
	p, S = [num for num in input().split(' ')]
	p = int(p)
    
	if done[p-1] == False:
		if S == 'AC':
			done[p-1]=True
			suc+=1
		else:
			ans[p-1]+=1
	else: # done[p-1] == True
		if S == 'AC':
			pass
		else:
			pass

pen = 0
for i, ans_i in enumerate(ans):
	if done[i]==True: pen+=ans_i

print('{} {}'.format(suc, pen))

Measured memory_bytes: 4760
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    ll n, h, a, b;
    cin >> n >> h;
    ll simple_atk = 0;
    vector<ll> big_trick;
    for(int i = 0; i < n; i++) {
        cin >> a >> b;
        big_trick.push_back(b);
        simple_atk = max(simple_atk, a);
    }
    ll ans = 0;
    sort(big_trick.begin(), big_trick.end());
    for(int i = n-1; i >= 0; i--) {
        if (big_trick[i] > simple_atk) {
            h -= big_trick[i];
            ans += 1;
            if (h <= 0) {
                cout << ans << endl;
                return 0;
            }
        } else {
            break;
        }
    }
    ans += 1+(h-1)/simple_atk;
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 1400
import java.util.*;
import java.math.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    char s[][] = new char[h+2][w+2];

    for (int i = 1; i <= h; i++) {
      String line = sc.next();
      for (int j = 1; j <= w; j++) {
        s[i][j] = line.charAt(j-1);
      }
    }

    for (int i = 1; i <= h; i++) {
      for (int j = 1; j <= w; j++) {
        if (s[i][j] == '#') {
          if (s[i-1][j] == '#') continue;
          if (s[i+1][j] == '#') continue;
          if (s[i][j-1] == '#') continue;
          if (s[i][j+1] == '#') continue;
          System.out.println("No");
          return;
        }
      }
    }

    System.out.println("Yes");

  }

}


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

int main() {
  int n,h,x,z;
  cin >> n >> h;
  vector<int> c(n);
  vector<int> d(n);
  bool y = true;
  for(int i=0;i<n;i++){
    cin >> c.at(i) >> d.at(i);
  }
  sort(c.begin(), c.end());
  reverse(c.begin(), c.end());
  sort(d.begin(), d.end());
  reverse(d.begin(), d.end());
  
  for(int i=0;i<n;i++){
    if(c.at(0) <= d.at(i)){
      z = i+1;
    }
    else{
      break;
    }
  }
  
  for(int i=0;i<z;i++){
    h -= d.at(i);
    if(h <=0){
      cout << i+1 << endl;
      y = false;
      break;
    }
  }
  
  if(y){
    x = h/c.at(0);
    if(h%c.at(0) > 0){
      x++;
    }
    cout << x + z << endl;
  }
}


Measured memory_bytes: 1024
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

tuplify2 (x : y : _) = (x, y)
tuplify2 _ = undefined

readInt = fst . fromJust . BS.readInt

readIntTuple = tuplify2 . map readInt . BS.words

getIntTuple = readIntTuple <$> BS.getLine

main = getIntTuple >>= \xs -> print $ maximum [0, fst xs - snd xs * 2]


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

using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if ((a - b == 0 && c != a) || ((b - c) == 0 && a != c) || ((a - c) == 0 && b != c))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import sys

def f(x):
    return x**2

def integral(d):
    s = 0
    for _d in range(1, int(600/d)):
        s += f(d * _d) * d
    return s

def run():
    for d in sys.stdin:
        print(integral(int(d)))

if __name__ == '__main__':
    run()




Measured memory_bytes: 5604
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
	Scanner sc=new Scanner(System.in);
	int n=sc.nextInt();
	int []a=new int [n];
	for(int i=0;i<n;i++)
		a[i]=sc.nextInt();
	
	int start=0;
	int end=0;
	int v=0;
	long s=0;
	long ans=0;
	boolean f=true;
	while(end<n)
	{
		if(f)
		{	
			s+=a[end];
			v^=a[end];
		}
		//System.out.println(start+" "+end+" "+s+" "+v);
		if(s==v)
		{	
			f=true;
			end++;
		}	
		else
		{
			f=false;
			long len=end-start;
			ans+=len;
			s-=a[start];
			v^=a[start];
			start++;
			
		}
		
		
				
	}

	if(f)
	{
		long len=(end-start);
		ans+=(len)*(len-1)/2;
		ans+=len;
	}
	
	System.out.println(ans);	
		
	

	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		public Scanner(InputStream s)
		{
			br=new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String s) throws FileNotFoundException
		{
			br=new BufferedReader(new FileReader(s));
		}
	
		public String nextLine() throws IOException
		{
			return br.readLine();
		}
		public String next() throws IOException
		{
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
			
		}
		public double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException
		{
			return br.ready();
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
	}
}


Measured memory_bytes: 45556
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[150];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n,cmp);
    int sum=0;
    for(int i=0;i<k;i++)
    {
        sum+=a[i];
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

type ShopEntry struct {
	Price    int
	BuyLimit int
}

type ShopEntries []ShopEntry

func (p ShopEntries) Len() int {
	return len(p)
}

func (p ShopEntries) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p ShopEntries) Less(i, j int) bool {
	return p[i].Price < p[j].Price
}

func main() {
	var (
		In        = ReadLineInt()
		ShopCount = In[0]
		Shops     = make([]ShopEntry, 0)
		Target    = In[1]
	)

	for i := 0; i < ShopCount; i++ {
		Input := ReadLineInt()
		Shops = append(Shops, ShopEntry{
			Input[0],
			Input[1],
		})
	}

	sort.Sort(ShopEntries(Shops))

	Result := 0
	for _, v := range Shops {
		Price := v.Price
		BuyLimit := v.BuyLimit

		if BuyLimit >= Target {
			Result += Price * Target
			//fmt.Println(Price, Target)
			break
		}

		Result += Price * BuyLimit
		Target -= BuyLimit
		//fmt.Println(Price, BuyLimit)
	}

	fmt.Println(Result)
}

/////////////////////////////////////////

func fln(format string, elements ...interface{}) {
	fmt.Printf(format+"\n", elements...)
}

var BufReader = bufio.NewReaderSize(os.Stdin, 1e6)

func ReadLine() string {
	a, _, _ := BufReader.ReadLine()
	return string(a)
}

func ReadLineInt() (result []int) {
	in := strings.Split(ReadLine(), " ")
	result = make([]int, 0, 2)
	for _, v := range in {
		t, _ := strconv.Atoi(v)
		result = append(result, t)
	}
	return
}

Measured memory_bytes: 8448
n = int(input())
a = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s = s[1:]

# 0th: positive
ans1 = 0
c = [0]
for i in range(n):
    if i % 2 == 0:
        _b = max(1 - s[i] - c[-1], 0)
    else:
        _b = min(-1 - s[i] - c[-1], 0)
    c.append(c[-1] + _b)
    ans1 += abs(_b)

# 0th: negatie
ans2 = 0
c = [0]
for i in range(n):
    if i % 2 != 0:
        _b = max(1 - s[i] - c[-1], 0)
    else:
        _b = min(-1 - s[i] - c[-1], 0)
    c.append(c[-1] + _b)
    ans2 += abs(_b)

print(min(ans1, ans2))


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

using namespace std;

struct UnionFind{
private:
    std::vector<int> par;
    std::vector<int> rank;
public:
    UnionFind(int size){
        par=std::vector<int>(size);
        rank=std::vector<int>(size);
        for(int i=0;i<size;++i){
            par[i]=i;
            rank[i]=1;
        }
    }

    int root(int x){
        if(par[x]==x)return x;
        else {
            par[x]=root(par[x]);
            return par[x];
        }
    }

    bool same(int x,int y){//0-indexed
        return root(x)==root(y);
    }

    void unite(int x,int y){//0-indexed
        x=root(x);
        y=root(y);
        if(x==y)return;

        if(rank[x]<rank[y]){
            par[x]=y;
        }
        else{
            par[y]=x;
            if(rank[x]==rank[y])++rank[x];
        }
    }
};

int main(){
    int n,m;
    cin>>n>>m;
    UnionFind uf(n);
    int x,y,z;
    int ans=0;
    for (int i = 0; i < m; ++i) {
        cin>>x>>y>>z;
        --x;--y;z=z%2+2;
        uf.unite(x,y);
    }
    set<int> st;
    for (int i = 0; i < n; ++i) {
        int t=uf.root(i);
        if(st.find(t)==st.end()){
            ++ans;st.insert(t);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5760
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e6+10;
int a[maxn];
int pri[maxn],vis[maxn];
int gcd(int a, int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
bool work(){
    for(int i=0; i<maxn; i++)pri[i]=1;
    pri[1]=pri[0]=0;
    for(int i=2; i<maxn; i++){
        if(pri[i]){
            int val=vis[i];
            for(int j=i*2; j<maxn; j+=i){
                pri[j]=0;
                val+=vis[j];
            }
            if(val>1)return false;
        }
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i],vis[a[i]]++;
    if(work()){
        cout<<"pairwise coprime"<<endl;
        return 0;
    }
    int ans=a[1];
    for(int i=1; i<=n; i++)ans=gcd(ans,a[i]);
    if(ans==1)cout<<"setwise coprime"<<endl;
    else cout<<"not coprime"<<endl;
    return 0;
}


Measured memory_bytes: 14752
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;
double dat[100][100];
int dp[6][1010];//動的計画法
int prime[10000001];
char str[1010][1010];
vector<pair<int,int> > pc[100001];
int ABS(int a){return max(a,-a);}
int main(){
  int n,m,tmp;
  while(cin>>n>>m,n){
	  vector<pair<int,int> > place(m);
	  for(int i=0;i<m;i++) {
		 place[i].second = i+1;
		 place[i].first = 0;
	  }
	  for(int i=0;i<n;i++){
		  for(int j=0;j<m;j++){
			  cin>>tmp;
			  place[j].first -=tmp;
		  }
	  }
	  sort(place.begin(),place.end());
		for(int i=0;i<m;i++) cout<<(i?" ":"")<<place[i].second;
		cout<<endl;
  }
    return 0;
}


Measured memory_bytes: 5384
#include <iostream>
using namespace std;
const int nm=200005;
int v[nm];
int ap[30][nm];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    char ch;
    int n=0;
    long long sum=0;
    while(1)
    {
        ch=cin.get();
        if(ch=='\n')
            break;
        n++;
        v[n]=ch-'a';
        ap[ch-'a'][n]++;
    }
    for(int i=0;i<26;i++)
        for(int j=n;j>=1;j--)
            ap[i][j]+=ap[i][j+1];
    for(int i=1;i<=n;i++)
        sum+=(n-i+1-ap[v[i]][i+1]-1);
    cout<<sum+1;
    return 0;
}


Measured memory_bytes: 21632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll a,b;
	cin>>a>>b;
	if(b%2!=0){
		cout<<"No";
	}
	else if(a==1){
		if(b==2||b==4){
			cout<<"Yes";
		}
		else{
			cout<<"No";
		}
	}
	else if(a!=1&&b%2==0){
		ll f=b/4;
		if(b%4!=0){
			f=f+1;
		}
		ll t=b/2;
		ll m=min(f,t);
		ll ma=max(f,t);
		if(a>=m&&a<=ma){
			cout<<"Yes";
		}
		else{
			cout<<"No";
		}
	}
	
	return 0;
}

Measured memory_bytes: 3636
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n, k = i_map()
    x = i_list()

    l = []
    r = []

    for i in x:
        if i < 0:
            l.append(-i)
        else:
            r.append(i)
    l.reverse()

    # if len(l) > 0:
    #     L = [l[0]]
    #     if len(l) > 1:
    #         for i in range(1, len(l)):
    #             L.append(L[i-1]+l[i])
    #
    # if len(r) > 0:
    #     R = [r[0]]
    #     if len(r) > 1:
    #         for i in range(1, len(r)):
    #             R.append(R[i-1]+r[i])


    R_len = len(r)
    L_len = len(l)

    ans = INF
    for i,j in enumerate(l):
        if R_len >= k - i - 1:
            if R_len == 0:
                ans = min(ans, j)
            else:
                ans = min(ans,2*j+r[k-i-2])

    for i,j in enumerate(r):
        if L_len >= k - i - 1:
            if L_len == 0:
                ans = min(ans,j)
            else:
                ans = min(ans,2*j+l[k-i-2])

    print(ans)


if __name__=="__main__":
    main()


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

int main() {
  int N,T, min = 10000, count = 0;
  
  cin>>N>>T;
  
  vector<int> c(N);
  vector<int> t(N);
  
  rep(i, N) cin>>c[i]>>t[i];
  
  rep(i, N){
    
    if(T>=t[i]){
      if(min>c[i]) min = c[i];
    }
    
  }
  
  if(min==10000) cout<<"TLE"<<endl;
  
  else cout<<min<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,m;
  cin>>n>>m;
  vector<string> c(n);
  rep(i,n) cin>>c[i];
  vector<string> a(n),b(n);
  string x(m,'.'),y(m,'.');
  rep(i,m) (i%2?x:y)[i]='#';
  a[0]=b[n-1]=string(m,'#');
  a[n-1]=b[0]=string(m,'.');
  reps(i,1,n-1) a[i]=x;
  reps(i,1,n-1) b[i]=y;
  
  rep(i,n)rep(j,m) if(c[i][j]=='#') a[i][j]=b[i][j]='#';
  rep(i,n) cout<<a[i]<<endl;
  cout<<endl;
  rep(i,n) cout<<b[i]<<endl;
  return 0;
}


Measured memory_bytes: 1536
def resolve():
    # WAの数はACを出した問題だけ数える
    N, M = map(int, input().split())

    ans = [False]*N
    WA = [0]*N
    ac, wa_tot = 0, 0
    for _ in range(M):
        q, s = input().split()
        q = int(q)-1
        if ans[q]:
            continue
        if s == "AC":
            ans[q] = True
            ac += 1
            wa_tot += WA[q]
        if s == "WA":
            WA[q] += 1

    print(ac, wa_tot)

if __name__ == "__main__":
    resolve()

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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define fir first
#define sec second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read()
{
    register int _, __; register char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}

inline void File()
{
#ifdef hany01
    freopen("agc021d.in", "r", stdin);
    freopen("agc021d.out", "w", stdout);
#endif
}

const int maxn = 310;

char s[maxn];
int n, k, f[maxn][maxn][maxn];

int main()
{
    File();
    scanf("%s", s + 1), n = strlen(s + 1), k = read();
    For(len, 1, n)
        For(st, 1, n - len + 1) {
            register int ed = st + len - 1;
            For(i, 0, k) {
                if (st == ed) f[st][ed][i] = 1;
                else if (st + 1 == ed) f[st][ed][i] = i || s[st] == s[ed] ? 2 : 1;
                else {
                    f[st][ed][i] = max(f[st + 1][ed][i], f[st][ed - 1][i]);
                    if (s[st] == s[ed]) chkmax(f[st][ed][i], f[st + 1][ed - 1][i] + 2);
                    if (i) chkmax(f[st][ed][i], f[st + 1][ed - 1][i - 1] + 2);
                }
            }
        }
    printf("%d\n", f[1][n][k]);
    return 0;
}

Measured memory_bytes: 114560
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, tmp;
  int a[101];
  int alice = 0;
  int bob = 0;
  int count = 1;
  cin >> n;
  for(int i = 0; i < n; i++)cin >> a[i];
  tmp = a[0];
  for(int i = 1; i <= n; i++){
    tmp = a[0];
    for(int j = 0; j < n; j++){
      tmp = max(tmp, a[j]);
    }
    if(i % 2 != 0){
      alice += tmp;
      for(int j = 0; j < n; j++){
        if(tmp == a[j]){
          a[j] = 0;
          break;
        }
      }
    }
    else{
      bob += tmp;
      for(int j = 0; j < n; j++){
        if(tmp == a[j]){
          a[j] = 0;
          break;
        }
      }
    }
  }
  //cout <<alice <<endl << bob << endl;
  cout << alice - bob << endl;
}

Measured memory_bytes: 3608
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

quickSortVec l u arr
  | l >= u    = return ()
  | otherwise = do
      VM.unsafeSwap arr l ((u+l)`div`2)
      t <- VM.unsafeRead arr l
      let i = l
          j = u + 1
      nj <- loopVec t u i j arr
      VM.unsafeSwap arr l nj
      quickSortVec l (nj-1) arr
      quickSortVec (nj+1) u arr

loopVec !t !u !i !j arr = do
  ni <- doWhile i (+1)         (< t)
  nj <- doWhile j (subtract 1) (> t)
  if ni > nj
    then return nj
    else do VM.unsafeSwap arr ni nj
            loopVec t u ni nj arr
              where
                {-# INLINE doWhile #-}
                doWhile k op p
                  | nk > u    = return nk
                  | otherwise = do
                      x <- VM.unsafeRead arr nk
                      if p x then
                        doWhile nk op p
                        else
                        return nk
                        where
                          nk = op k

main = do
  n <- getInt
  as'' <- getIntVec n
  as' <- V.thaw as''
  quickSortVec 0 (n-1) as'
  as <- V.freeze as'

  let s = Set.fromList [(as V.! (n-1), 1)]

      solve i s j res
        | i > n = res
        | otherwise =
            let a = as V.! (n-i)
                ((score, _), s') = Set.deleteFindMax s
                s''  = (a, j) `Set.insert` s'
                s''' = (a, j+1) `Set.insert` s''
            in solve (i+1) s''' (j+2) (res+score)

      ans = solve 2 s 2 0

  print ans


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

using namespace std;

int main()
{ string s ,a[7];
  cin >> s;
   if ( s=="MON") cout<<6;
      if ( s=="TUE") cout<<5;
         if ( s=="WED") cout<<4;
            if ( s=="THU") cout<<3;
               if ( s=="FRI") cout<<2;
                  if ( s=="SAT") cout<<1;
                     if ( s=="SUN") cout<<7;

    return 0;
}


Measured memory_bytes: 256
unittest
{
	assert( [ "TSTTSS" ].parse.expand.solve == 4 );
	assert( [ "SSTTST" ].parse.expand.solve == 0 );
	assert( [ "TSSTTTSS" ].parse.expand.solve == 4 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto x = input.front.to!( dchar[] );
	return tuple( x );
}

auto solve( dchar[] x )
{
	auto ans = x.length.signed;
	auto i = 0L;
	auto s = 0L;
	auto t = 0L;
	while( i < x.length )
	{
		for( ; i < x.length && x[ i ] == 'S'; i++ ) s++;
		for( ; i < x.length && x[ i ] == 'T'; i++ ) t++;
		if( s <= t )
		{
			ans -= s * 2;
			s = 0;
			t = 0;
		}
		else
		{
			ans -= t * 2;
			s -= t;
			t = 0;
		}
	}
	return ans;
}


Measured memory_bytes: 3512
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>


using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast_cin() ios_base::sync_with_stdio(false);

typedef long long ll;

const int INF = 1e7;
const int MAX_SIZE = 1e5 + 10;

vector<int> graph[MAX_SIZE];
vector<bool> visited;

vector<int> LIST;

void bfs(int s, int n, vector<int> &d)
{
	for(int i = 1; i<= n; i++)
	{
		visited[i] = false;
		d[i] = INF;
	}
	visited[s] = true;
	queue<int> q1;
	q1.push(s);
	d[s] = 0;
	while(!q1.empty())
	{
		int u = q1.front();
		q1.pop();
		for(auto &v: graph[u])
		{
			if(!visited[v])
			{
				visited[v] = true;
				d[v] = d[u] + 1;
				q1.push(v);
			}
		}
	}
}

int main()
{
	int n;
	cin >> n;
	int x, y;
	for(int i = 1; i < n; i++)
	{
		cin >> x >> y;
		graph[x].pb(y);
		graph[y].pb(x);
	}
	vector<int> d1, dN;
	d1.resize(n + 1);
	dN.resize(n + 1);
	visited.resize(n + 1);
	bfs(1, n, d1);
	bfs(n, n, dN);
	int b = 0 , w = 0;
	for(int i = 1; i <= n; i++)
	{
		if(d1[i] <= dN[i])
			b++;
		else if(d1[i] > dN[i])
			w++;
	}
	// cout << ÷
	if(w >= b)
		cout << "Snuke" << endl;
	else
		cout << "Fennec" << endl;
	return 0;
}

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

int main(){
  int n,m;
  cin >> n >> m;
  vector<pair<int,int>> p(m);
  for(int i=0; i<m; i++)
    cin >> p[i].first >> p[i].second;
  for(int x=0; x<1000; x++){
    int keta =1;
    int nx = x/10;
    vector<int> d(1,x%10);
    while(nx){
      keta++;
      d.push_back(nx%10);
      nx/=10;
    }
    if(keta!=n)continue;
    bool ok=true;
    reverse(d.begin(),d.end());
    for(int i=0; i<m; i++)
      if(d[p[i].first-1]!=p[i].second) ok=false;
    if(ok){
      cout << x << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
namespace LCY{
	#define double long double
	const double EPS=1e-10;
	inline int dcmp(double x){if(fabs(x)<EPS)return 0;return (x<0)?-1:1;}
	struct Point{double x,y;Point(double _x=0,double _y=0){x=_x;y=_y;}};
	struct Vector{double x,y;Vector(double _x=0,double _y=0){x=_x;y=_y;}};
	
	Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
	Vector operator * (Vector a,double d){return Vector(a.x*d,a.y*d);}
	Point operator + (Point a,Vector b){return Point(a.x+b.x,a.y+b.y);}
	
	inline double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
	inline double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
	inline double norm(Vector a){return dot(a,a);}
	
	struct Line{
		Point p1,p2;
		Line(Point _p1=Point(0,0),Point _p2=Point(0,0)){p1=_p1;p2=_p2;}
	};
	inline bool is_parallel(Line l1,Line l2){return dcmp(cross(l2.p2-l2.p1,l1.p2-l1.p1))==0;}
	inline bool is_vertical(Line l1,Line l2){return dcmp(dot(l2.p2-l2.p1,l1.p2-l1.p1))==0;}
	
	Point project(Line l,Point p){
		Vector base=l.p2-l.p1;
		double r=dot(p-l.p1,base)/norm(base);
		return l.p1+base*r;
	}
	Point reflect(Line l,Point p){
		Point q=project(l,p);
		Vector v=p-q;v.x=-v.x;v.y=-v.y;
		return q+v;
	}
	int ccw(Vector v1,Vector v2){
		if(dcmp(cross(v1,v2))>0)return 1;//COUNTER_CLOCKWISE
		else if(dcmp(cross(v1,v2))<0)return 2;//CLOCKWISE
		else{
			if(dcmp(dot(v1,v2))<0)return 3;//ONLINE_BACK
			else{
				if(dcmp(norm(v1)-norm(v2))<0)return 4;//ONLINE_FRONT
				else return 5;//ON_SEGMENT
			}
		}
	}
	inline bool is_inter(Line l1,Line l2){
		bool flag=1;
		int t1=ccw(l1.p2-l1.p1,l2.p1-l1.p1),t2=ccw(l1.p2-l1.p1,l2.p2-l1.p1);
		if(t1==5 || t2==5) return true;
		else if(t1==t2)return false;
		else if(t1>=3 && t2<=2) return false;
		else if(t1<=2 && t2>=3) return false;
		swap(l1,l2);
		t1=ccw(l1.p2-l1.p1,l2.p1-l1.p1),t2=ccw(l1.p2-l1.p1,l2.p2-l1.p1);
		if(t1==5 || t2==5) return true;
		else if(t1==t2)return false;
		else if(t1>=3 && t2<=2) return false;
		else if(t1<=2 && t2>=3) return false;
		return true;
	}
}
using namespace LCY;
int main(){
	int n;cin>>n;while(n--){
		Point p1,p2,p3,p4;
		cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y>>p4.x>>p4.y;
		cout<<(is_inter(Line(p1,p2),Line(p3,p4)))<<endl;
	}
	return 0;
}


Measured memory_bytes: 3236
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>

using namespace std;
using namespace __gnu_pbds;

typedef
tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> orderedSet;

#define pb push_back
#define F first
#define S second
#define all(a) (a).begin(), (a).end()

#define for1(i0, l0, r0) for (int i0 = l0; i0 < r0; ++i0)
#define for2(i0, l0, r0) for (int i0 = l0; i0 <= r0; ++i0)
#define forn(i0, n0) for (int i0 = 0; i0 < n0; ++i0)
#define forn1(i0, n0) for (int i0 = 1; i0 < n0; ++i0)
#define forr(i0, n0) for (int i0 = n0; i0 >= 0; --i0)
#define forr1(i0, r0, l0) for (int i0 = r0; i0 > l0; --i0)
#define forr2(i0, r0, l0) for (int i0 = r0; i0 >= l0; --i0)

#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define relaxMax(a, b) a = max(a, b)
#define relaxMin(a, b) a = min(a, b)

typedef long long ll;
typedef long double ld;
#define ui unsigned int
#define ull unsigned long long

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<string> vs;

typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;

typedef vector<vi> vvi;
typedef vector<vd> vvd;
typedef vector<vll> vvll;
typedef vector<vb> vvb;

#define vpss vector<pss>
#define vvs vector<vs>
#define vvpii vector<vpii>
#define vvpll vector<vpll>
#define vpt vector<pt>
#define vvvi vector<vvi>
#define vsi vector<set<int>>
#define ss second
#define ff first

#define printvi(arr) for (int x0 : arr) cout << x0 << ' '; cout << '\n';
#define printvll(arr) for (ll x0 : arr) cout << x0 << ' '; cout << '\n';
#define printpair(pair0) cout << pair0.F << ' ' << pair0.S << '\n';
#define printvp(arr) for (auto pair0 : arr) printpair(pair0);
#define initArray(arr, N0, X0) memset(arr, X0, N0 * sizeof(int))
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void init() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout.precision(16);
    //freopen("amusing.in", "r", stdin);
    //freopen("amusing.out", "w", stdout);
}

void solve() {
    int n;
    cin >> n;
    int ans = 1e9;
    vi a(n);
    forn(i, n) cin >> a[i];
    for2(x, -100, 100){
        int sum = 0;
        forn(i, n) sum += (a[i] - x) * (a[i] - x);
        ans = min(ans, sum);
    }
    cout << ans << '\n';
}

bool multitest = false;

int main() {
    init();
    int t = 1;
    if (multitest) cin >> t;
    forn(i, t) solve();
}

Measured memory_bytes: 3640
package main

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

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	x := scanInt()

	for i := 2; i < 1000000008; i++ {
		if factorization(int64(i))[int64(i)] == 1 {
			if x <= i {
				fmt.Println(i)
				return
			}
		}
	}

}

func factorization(n int64) map[int64]int {
	res := make(map[int64]int, 0)
	for i := int64(2); i*i <= n; i++ {
		for n%i == 0 {
			res[i]++
			n /= i
		}
	}
	if n!=1 {
		res[n] = 1
	}
	return res
}


Measured memory_bytes: 5504
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <complex>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cerr<<"# "<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;

int DreyfusWagner(const vvi& _dist,const vi& ts)
{
	int n=_dist.size();
	vvi dist=_dist;
	rep(k,n) rep(i,n) rep(j,n)
		dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	
	int tsize=ts.size();
	vvi dp(1<<tsize,vi(n,INFTY));
	rep(i,tsize) rep(j,n)
		dp[1<<i][j]=dist[ts[i]][j];
	rep(i,1<<tsize){
		for(int j=i;j;j=i&(j-1)) rep(k,n)
			dp[i][k]=min(dp[i][k],dp[j][k]+dp[i^j][k]);
		rep(j,n) rep(k,n)
			dp[i][j]=min(dp[i][j],dp[i][k]+dist[k][j]);
	}
	return *min_element(all(dp.back()));
}

int main()
{
	for(int h,w;scanf("%d%d",&h,&w),h|w;){
		int n=h*w;
		vvi dist(n,vi(n,INFTY));
		vi hs;
		rep(i,h) rep(j,w){
			int x; scanf("%d",&x);
			if(x==1)
				hs.push_back(i*w+j);
			dist[i*w+j][i*w+j]=0;
			int di[]={-1,1,0,0},dj[]={0,0,-1,1};
			rep(k,4){
				int ii=i+di[k],jj=j+dj[k];
				if(0<=ii && ii<h && 0<=jj && jj<w)
					dist[i*w+j][ii*w+jj]=dist[ii*w+jj][i*w+j]=1;
			}
		}
		int res=DreyfusWagner(dist,hs);
		printf("%d\n",n-(res+1));
	}
	
	return 0;
}

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

  int main(){
    long long N,a[5];
    cin >> N;
    for (int i;i<5;i++){
      cin >> a[i];
    }
    sort(a,a+5);
    cout << (N+a[0]-1)/a[0]+4 << endl;
  }


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>

#define f first
#define s second
#define mp make_pair

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

using namespace std;

typedef unsigned int uint;
typedef long long ll;

int sb[10][10000];

#define MAX (50000000)

int main(){
  int n,k;
  while(scanf("%d%d",&n,&k), n+k){
    int dist[n][n];
    REP(i,n) REP(j,n) dist[i][j] = MAX;
    REP(i,n) dist[i][i] = 0;
    while(k --> 0){
      int s; scanf("%d",&s);
      if(s == 0){
        int a,b;
        scanf("%d%d",&a,&b); a--; b--;
        if(dist[a][b] == MAX) puts("-1");
        else printf("%d\n",dist[a][b]);
      }else{
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c); a--; b--;
        if(dist[a][b] < c) continue;
        dist[a][b] = dist[b][a] = c;
        REP(i,n){
          dist[a][i] = dist[i][a] = min(dist[a][i], dist[a][b] + dist[b][i]);
          dist[b][i] = dist[i][b] = min(dist[b][i], dist[b][a] + dist[a][i]);
        }
        REP(i,n) REP(j,n){
          dist[i][j] = min(dist[i][j], dist[i][a] + dist[a][j]);
          dist[i][j] = min(dist[i][j], dist[i][b] + dist[b][j]);
        }
      }
    }
  }
  return 0;
}

Measured memory_bytes: 924
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>

#define REP(i,n) for(int i=0;i<(n);i++)
#define EPS (1e-7)
#define INF (2e9)

using namespace std;
typedef long long int ll;

int N, B[102];
int main(void){
    cin >> N;
    B[0] = INF;
    for(int i=1;i<N;i++) cin >> B[i];
    B[N] = INF;

    int res = 0;
    REP(i, N) res += min(B[i],B[i+1]);
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin>>x;
    if(x>=400&&x<=599)
    {
        cout<<8<<endl;
    }
    else if(x>=600&&x<=799)
    {
        cout<<7<<endl;
    }
    else if(x>=800&&x<=999)
    {
        cout<<6<<endl;
    }
    else if(x>=1000&&x<=1199)
    {
        cout<<5<<endl;
    }
    else if(x>=1200&&x<=1399)
    {
        cout<<4<<endl;
    }
    else if(x>=1400&&x<=1599)
    {
        cout<<3<<endl;
    }
    else if(x>=1600&&x<=1799)
    {
        cout<<2<<endl;
    }
    else if(x>=1800&&x<=1999)
    {
        cout<<1<<endl;
    }
    return 0;
}

Measured memory_bytes: 3568
#include<iostream>
using namespace std;
int main(void){
	int W, H, x, y, r, X, Y, Xx, Yy;
	cin >> W >> H >> x >> y >> r;
	X = x + r;
	Y = y + r;
	Xx = x - r;
	Yy = y - r;
	if(0 <= Xx && W >= X && 0 <= Yy && H >= Y){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
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 = float('INF')

#A
def A():
    a = ["a", "i", "u", "e", "o"]
    c = S()
    if c[0] in a:
        print("vowel")
    else:
        print("consonant")
    return

#B
def B():
    _ = II()
    t = LI()
    tsum = sum(t)
    for _ in range(II()):
        p, x = LI()
        print(tsum - t[p - 1] + x)
    return

#C
def C():
    s = input()
    lens = len(s)
    check = ["dream", "dreamer", "erase", "eraser"]
    q = deque()
    q.append(0)
    while q:
        p = q.pop()
        if p == lens:
            print("YES")
            return
        for i in check:
            if s[p:p + len(i)] == i:
                q.appendleft(p + len(i))
    print("NO")
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()


Measured memory_bytes: 41712
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;


    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int H=N/3600;
        int M=(N%3600)/60;
        int S=(N-3600*H-60*M);
        Console.WriteLine(H+":"+M+":"+S);
    }


}
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }

}


Measured memory_bytes: 15928
#include "bits/stdc++.h"
using namespace std;

#define rep(i,N) for(int i=0;i<(int)N;++i)
#define rep1(i,N) for(int i=1;i<=(int)N;++i)

using int64 = long long;
using i64 = long long;

#define int long long

const int inf = 1 << 30;
const i64 inf64 = 1ll << 60;

const int mod = 1e9 + 7;

int dp[100010][2];

int mod_pow(int x, int y, const int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) (res *= x) %= mod;
		(x *= x) %= mod;
		y >>= 1;
	}
	return res;
}

int calc_mod(int x, int m) {
	int res = x % m;
	if (res < 0) res += m;
	return res;
}

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

	dp[0][0] = 1;
	for (int i = 1; i <= N; ++i) {
		(dp[i][0] += dp[i - 1][0] + dp[i - 1][1]) %= mod;
		(dp[i][1] += dp[i - 1][0] + dp[i - 1][1]) %= mod;
		if (i - M >= 0) {
			dp[i][1] = (dp[i][1] - dp[i - M][0] + mod) % mod;
		}
	}

	cout << calc_mod((mod_pow(2, N, mod) - (dp[N][0] + dp[N][1]) + mod), mod) << endl;
}


Measured memory_bytes: 4624
/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n;
  cin >> n;
  int up = (n + 1000 - 1) / 1000;
  int cur = 1000 * up;
  cout << cur - n << '\n';
  return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
//priority_queue<int>q1;
char a[102][102];
void fucked(int x,int y)
{
	if(a[x+1][y]!='#')
		a[x+1][y]++;
	if(a[x-1][y]!='#')
		a[x-1][y]++;
	if(a[x][y+1]!='#')
		a[x][y+1]++;
	if(a[x][y-1]!='#')
		a[x][y-1]++;
	if(a[x+1][y+1]!='#')
		a[x+1][y+1]++;
	if(a[x+1][y-1]!='#')
		a[x+1][y-1]++;
	if(a[x-1][y+1]!='#')
		a[x-1][y+1]++;
	if(a[x-1][y-1]!='#')
		a[x-1][y-1]++;
}
int main()
{
	int x,y;
	cin>>x>>y;
	for(int i=1;i<=x;i++)
		for(int j=1;j<=y;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='.')
				a[i][j]='0';
		}
	for(int i=1;i<=x;i++)
		for(int j=1;j<=y;j++)
			if(a[i][j]=='#')
				fucked(i,j);
	for(int i=1;i<=x;i++)
	{
		for(int j=1;j<=y;j++)
			cout<<a[i][j];
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int A = 1;
	int B = 0;
	int C = 0;
	char conma;
	char c[4];
	int swap;
	
	while(scanf("%s", c) != EOF){
		swap = 0;
		switch(c[0]){
			case 'A':
			if (c[2] == 'B'){
				swap = A;
				A = B;
				B = swap;
			}
			else if (c[2] == 'C'){
				swap = A;
				A = C;
				C = swap;
			}
			break;
			case 'B':
			if (c[2] == 'A'){
				swap = B;
				B = A;
				A = swap;
			}
			else if (c[2] == 'C'){
				swap = C;
				C = B;
				B = swap;
			}
			break;
			case 'C':
			if (c[2] == 'B'){
				swap = C;
				C = B;
				B = swap;
			}
			else if (c[2] == 'A'){
				swap = A;
				A = C;
				C = swap;
			}
			break;
		}
	}
	
	if (A){
		printf("A\n");
	}
	else if(B){
		printf("B\n");
	}
	else {
		printf("C\n");
	}
	
	return (0);
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int k;
  cin>>k;

  int a[n];

  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  int dp[n+109];
  dp[0]=0;
  for(int i=1;i<n+109;i++)
  {
    dp[i]=INT_MAX;
  }
  //dp[1]=abs(a[1]-a[0]);
  for(int i=0;i<n;i++)
  {
    for(int j=i;j<=i+k;j++)
    if(j<n){
      dp[j]=min(dp[i]+abs(a[j]-a[i]),dp[j]);
    }

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
#define MOD 1000000007LL;
LL bas=29LL;

int n;
map<PLL,LL> mp;
string s;

int main()
{
    cin>>n>>s;
    for(int i=0;i<(1<<n);i++)
    {
        LL x=0,y=0;
        for(int j=0;j<n;j++)
        {
            if((i&(1<<j)))x=(x*bas+(s[j]-'a'+1))%MOD;
        }
        for(int j=n-1;j>=0;j--)
        {
            if((i&(1<<j))==0)y=(y*bas+(s[j]-'a'+1))%MOD;
        }
        mp[make_pair(x,y)]++;
    }
    LL ans=0;
    for(int i=0;i<(1<<n);i++)
    {
        LL x=0,y=0;
        for(int j=0;j<n;j++)
        {
            if((i&(1<<j)))x=(x*bas+(s[j+n]-'a'+1))%MOD;
        }
        for(int j=n-1;j>=0;j--)
        {
            if((i&(1<<j))==0)y=(y*bas+(s[j+n]-'a'+1))%MOD;
        }
        ans+=mp[make_pair(y,x)];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 33024
//ysh_gpta
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
typedef long long ll;
#define vb vector<bool>
#define vi vector<ll>
#define vvi vector<vi>
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define mkp make_pair
#define pb push_back
#define INF 1000000000000000
#define MOD 1000000007
#define ff first
#define ss second
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//ll gcd( ll a, ll b ){if(b==0) return a; else return gcd( b, a%b );}
//ll ncr(ll n,ll r){ll ans=1;r=min(r,n-r);for (int i=1;i<=r;i++){ans*=(n-r+i);ans/=i;}return ans;}
//void printArray(vi &v){for(int i=0;i<v.size();i++) cout<<v[i]<<endl; cout<<endl; }
int main(){
   FastIO
   ll n,W;
   	cin>>n>>W;
    ll mxV = 0;
	ll w[n],v[n];
	for(int i=0; i<n; i++){
		cin >> w[i] >> v[i];
		mxV += v[i];
	}
	
	ll dp[mxV+1];
	for(ll i=0; i<=mxV; i++)dp[i]=1e18;
	dp[0] = 0;
	for(int i=0; i<n; i++){
		for(ll j=mxV; j >= v[i]; j--){
			dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
			//cout << i << ' ' << j << ' ' << dp[j] << endl;
		}
	}
	for(ll i=mxV; i>=0; i--){
		if(dp[i]<=W){
			cout << i << endl;
			break;
		}
	}
   return 0;
}

Measured memory_bytes: 1024