akhauriyash/Code-Regression huggingface dataset:
open Str
open List

let get_int () = int_of_string (read_line ());;

let rec to_int sep =
    match sep with 
    | [] -> []
    | a :: b -> 
            (int_of_string a) :: (to_int b);;

let rec to_color rates =
    match rates with
    | [] -> []
    | fst :: rst -> (fst / 400) :: (to_color rst)

let rec print_int_arr arr =
    match arr with
    | [] -> ()
    | fst :: rst -> Printf.printf "%d\n" fst; print_int_arr rst;;

let get_int_arr () = 
    to_int (Str.split (Str.regexp " ") (read_line ()));;

let main =
    let _ = read_line () in
    let a = to_color (get_int_arr ()) in
    let const = List.length (List.sort_uniq (fun x y -> x - y) (List.filter (fun b -> b < 8) a)) in
    let change = List.length (List.filter (fun b -> b >= 8) a) in
    
    Printf.printf "%d " (if const == 0 then 1 else const);
    Printf.printf "%d\n" (const + change);


Measured memory_bytes: 384
import math


def main():
    N, K = map(int, input().split())
    d = []
    A = []

    for _ in range(K):
        d.append(int(input()))
        A.append(list(map(int, input().split())))

    sunuke = set(range(1, N+1))

    for a in A:
        for i in a:
            sunuke.discard(i)

    print(len(sunuke))





if __name__ == '__main__':
    main()


Measured memory_bytes: 9192
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<string>
#include<vector>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n0,n) for(int i=n0;i<n;i++)
#define Com(i,j,n) for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++)
#define W(x) cout<<x<<endl;
#define Debug(x) cout<<"#DEBUG "<<x<<endl;
#define INF (1<<29)
#define INF2 (long long)8*(long long)INF*(long long)INF
#define ll long long

using namespace std;


int min(int x,int y){if(y<x)return y;else return x;}
int max(int x,int y){if(y>x)return y;else return x;}
int fact(int x){int i=1;rep(j,x){i*=(j+1);} return i;}
long long fact(long long x){long long i=1;rep(j,x){i*=(j+1);} return i;}
int n,mid;
string s,lefts,rights;
int main()
{
    cin>>n;
    int left=0;
    cout<<0<<endl;
    cin>>lefts;
    if(lefts!="Vacant")
    {
        int right=n-1;
        cout<<n-1<<endl;
        cin>>rights;
        if(rights!="Vacant")
        {
            while(s!="Vacant")
            {
                mid=(left+right)/2;
                cout<<mid<<endl;
                cin>>s;
                if((mid-left)%2==0)
                {
                    if(s==lefts)
                    {
                        left=mid;
                        lefts=s;
                    }
                    else
                    {
                        right=mid;
                        rights=s;
                    }
                }
                else
                {
                    if(s!=lefts)
                    {
                        left=mid;
                        lefts=s;
                    }
                    else
                    {
                        right=mid;
                        rights=s;
                    }
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 852
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ld double 
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define BOOST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define all(v) v.begin(),v.end()
#define sl(a) a.size()
#define mod 1000000007 
#define lcm(a,b) (a*b)/__gcd(a,b)
#define MAX1 100006
#define f first
#define s second
#define pi 2*acos(0.0)
void solve()
{
    string str;   cin>>str;
    rep(i,0,sl(str)-1)
    {
        if(str[i+1]==str[i])
        {
            cout<<"Bad";
            exit(0);
        }
    }cout<<"Good";
}
int main()
{
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt","r",stdin);
    //for getting error from error.txt
    freopen("error.txt", "w", stderr);
    // for writing output to output.txt
    freopen("output.txt","w",stdout);
    #endif
    BOOST
    int T=1;  //cin>>T;
    while(T--) solve();
    cerr<<"Time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<"\n";
    cerr<<"My CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";
    return 0;
}


Measured memory_bytes: 3724
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

int cnt[512345][42] = {};

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K; cin >> N >> K;
    VL a(N); REP(i,N) cin >> a[i];
    VL accsum(N+1,0);
    REP(i,N){
        accsum[i+1] = accsum[i] + a[i];
    }

    VL kouho;
    FOR(i,0,N+1) FOR(j,i+1,N+1){
        kouho.eb(accsum[j]-accsum[i]);
    }

    sort(kouho.begin(),kouho.end());
    //cout << printVector(accsum) << endl;
    //cout << printVector(kouho) << endl;
    int len = kouho.size();
    int keta = 0;

    for(LL i = 2; i < (1LL << 42); i *= 2){
        REP(j,len){
            if(kouho[j]%2 == 0){
                cnt[j][keta] = 0;
            }
            else{
                cnt[j][keta] = 1;
            }

            kouho[j] /= 2;
        }
        keta++;
    }

    LL ans = 0;
    for(int i = keta; i >= 0; i--){
        int acc = 0;
        REP(j,len){
            if(cnt[j][i] == 1) {
                dump(j)
                dump(i)
                acc++;
            }
        }
        dump(acc)
        if(acc >= K){
            ans += LL(pow(2,i));
            REP(k,len){
                if(cnt[k][i] == 0){
                    dump(k)
                    REP(l,42) cnt[k][l] = 0;
                }
            }
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 88300
program main
character*16 :: a
integer :: x,i,j

x=0
read(*,*) a
do i=1,4
do j=1,4
if(a(i:i) == a(j:j)) then
	x = x + 1
end if
end do
end do
if (x==8) then
write(*,*) "Yes"
else 
write(*,*) "No"
end if

end program main

Measured memory_bytes: 256
from heapq import *
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A = sorted(A,reverse = True)
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

cake = []
heapify(cake)
for x in range(X):
  for y in range(min(Y,K//(x+1)+1)):
    for k in range(min(Z,K//((x+1)*(y+1))+1)):
      heappush(cake,-(A[x]+B[y]+C[k]))
for _ in range(K):
  print(abs(heappop(cake)))

Measured memory_bytes: 8596
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int A[100010];
int num[100010];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		//A[i] = 0;
		num[i] = -1;
	}
	int ans = 0;
	for (int i = N - 1; i >= 0; i--) {
		int ok = ans;
		int ng = -1;
		while (abs(ok - ng) > 1) {
			int mid = (ok + ng) / 2;
			if (A[i] < num[mid]) ok= mid;
			else ng = mid;
		}
		//cout << ok << endl;
		num[ok] = A[i];
		ans = max(ans, ok + 1);
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
mygcd :: Int -> Int -> Int
mygcd x y
    | r == 0    = y
    | otherwise = gcd y r
        where r = x `mod` y

solve :: [Int] -> String
solve [x, y] = (show $ mygcd x y) ++ "\n"

main :: IO ()
main = interact (solve . map read . words)

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

#define rep(l, r) for (int i = (l); i < (r); i++)

typedef long long ll;
 
using namespace std;

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

    cout << max(a + b, max(a - b, a * b)) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <cmath>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const double pi=acos(-1);

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

int main(){
    int n;
    cin >> n;
    vector<int> l(n);
    for(int i=0;i<n;i++) cin >> l[i];
    sort(l.begin(),l.end());
    int sum=0;
    for(int i=0;i<n-1;i++) sum+=l[i];
    if(l[n-1]<sum){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[5];
int main()
{
    int p,q,r,ans;
    cin>>p>>q>>r;
    a[1]=p;
    a[2]=q;
    a[3]=r;
    sort(a+1,a+4);
    cout<<a[1]+a[2]<<endl;
    return 0;
}


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



int main(){
    int N,K;
    cin >> N >>K;
    long long A=0ll;
    vector<int>vec(N);
    for(int i=0;i<N;i++){
        cin >> vec.at(i);
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<N-K;i++){
        A += vec.at(i);
    }
    cout << A << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int n,m,cnt=0,o,p,aa[220000],cntl=0,ab[220000];
pair<int,int> pp[220000];
string s="qwertyuiopl",ss[220000];
char c,cc[5000][5000]={};
queue<int> que;
signed main(){
    cin>>n;
    rep(i,n){
        cin>>ss[i];
    }
    sort(ss,ss+n);
    rep(i,n){
        if(s!=ss[i]){
            cnt++;
            s=ss[i];
        }
    }
    cout<<cnt;
}

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

#define F first
#define S second
#define nl '\n'
#define gcd __gcd
#define nset __builtin_popcount
#define pb push_back
#define btoe(x) x.begin(), x.end()
#define trim_chains(x) (x).resize(unique(btoe(x)) - (x).begin())
#define remove_dups(x) sort(btoe(x)); trim_chains(x);
#define rep(i, a, b)  for (int i = int(a); i <= int(b); i++)
#define nrep(i, a, b) for (int i = int(a); i >= int(b); i--)
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL)

using ll  = long long;
using ull = unsigned long long;
using vi  = vector<int>;
using vl  = vector<long>;
using vll = vector<ll>;
using vb  = vector<bool>;
using vvb = vector<vb>;
using vvi = vector<vector<int> >;
using ii  = pair<int, int>;
using vii = vector<ii>;
using vs  = vector<string>;
using msi = map<string, int>;
using iss = istringstream;

ll M = 1e9 + 7;

ll mod(ll x, ll M)
{
    ll res = x % M;
    return (res >= 0 ? res : res + M);
}

ll powmod(ll x, ll n, ll M)
{
    if(n == 0) return 1%M;
    ll half = powmod(x, n/2, M);
    if(n % 2 == 0) return (half*half)%M;
    return (((half*half)%M)*x)%M;
}

ll modinv(ll a, ll M)
{
    ll x = a, y = M;
    ll sx = 1, tx = 0;
    ll sy = 0, ty = 1;

    while(y != 0) {
        ll q = x/y;
        ll r = x%y;
        ll nsx = sy;
        ll ntx = ty;
        sy = sx - q*sy;
        ty = tx - q*ty;
        sx = nsx; tx = ntx;
        x = y; y = r;
    }

    if(sx < 0) sx += M;
    return sx;
}

vll ftable(2e6 + 1, 1);
ll fact(ll x)
{
    if(x <= 1) return 1;
    if(ftable[x] == 1) {
        ftable[x] = (x * fact(x-1)) % M;
    }
    return ftable[x];
}

ll combo(ll n, ll r)
{
    ll num = fact(n);
    ll denom = (fact(n - r) * fact(r))%M;
    ll dinv = modinv(denom, M);

    return (num * dinv) % M;
}

int main()
{
    FASTIO;
    int k; cin >> k;
    string s; cin >> s;
    int n = s.length();

    ll ans = 0;
    rep(i, 0, k) {
        ans += (combo(n + k, i + n) * powmod(25, k-i, M))%M;
        ans %= M;
    }

    cout << ans << nl;
    return 0;
}


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

using namespace std;

int main() {

    string S, T; cin >> S >> T;
    
    int res = 0;

   
    for(int i = 0; i < S.size(); i++) {
        if(S.at(i) != T.at(i)) {
            res++;
        }
    }

    cout << res << endl;  

    


    return 0;
}

Measured memory_bytes: 3848
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[]) {
  int k=0, x=0;
  int i=0;
  cin >> k>> x;
  for (i=x-k+1; i < k+x; i++) {
    cout << i << " ";
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String args[]){
        
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        char c = S.charAt(0);
        boolean flg = false;
        for(int i = 1; i < S.length(); i++){
            if(S.charAt(i) == c){
                flg = true;
                break;
            }
            c = S.charAt(i);
        }
        System.out.println(flg ? "Bad" : "Good");
        
    }
}


Measured memory_bytes: 24020
#include<bits/stdc++.h>
using namespace std;
#define MAX 100000
int n, m, x[MAX + 5], dis[MAX +5];

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0 ; i < m ; i++)
		scanf("%d", &x[i]);
	sort(x, x + m);
	int sum = 0;
	for(int i = 1 ; i < m ; i++){
		dis[i] = x[i] - x[i - 1];
	}
	sum = x[m - 1] - x[0];
	sort(dis, dis + m);
	int k = m - 1;
	for(int i = 0, k = m - 1 ; i < n - 1 && k >= 0; i++, k--){
		sum -= dis[k];
	}
	printf("%d\n", sum);
	
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <queue>
#include <stack>
#include <stdlib.h>
using namespace std;
#define rep(i,n) for (int i = 0; i <n; i++) 
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
int binary(int bina){
    int ans = 0;
    for (int i = 0; bina>0 ; i++)
    {
        ans = ans+(bina%2)*pow(10,i);
        bina = bina/2;
    }
    return ans;
}

using namespace std;
int main(){
    int n,i;std::cin >> n>>i;
    
   
    std::cout <<n-i+1 << std::endl;
    
    
}




Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

type ivec []int

func (v ivec) Len() int           { return len(v) }
func (v ivec) Less(i, j int) bool { return v[i] > v[j] }
func (v ivec) Swap(i, j int)      { v[i], v[j] = v[j], v[i] }

func main() {
	var n int
	fmt.Scan(&n)
	a := make(ivec, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}

	sort.Sort(a)

	alice := 0
	bob := 0
	for i := 0; i < n; i++ {
		if i % 2 == 0 {
			alice += a[i]
		} else {
			bob += a[i]
		}
	}

	fmt.Println(alice - bob)

}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=10e+7;
ll nature(ll a){
  if(a>=0){return(a);}
  else{return(-1*a);}
}
ll nCk(ll n,ll k){
  if((n&k)==k){return 1;}
  else{return 0;}
}
int main(){
  ll N,aa=0,ans=0;
  string str;
  cin>>N>>str;
  vector<ll> vec(N);
  for(ll i=0;i<N;i++){
    vec.at(i)=str.at(i)-'0'-1;
    if(vec.at(i)==1){aa++;}
    ans+=nCk(N-1,i)*(vec.at(i)%2);
  }
  if(ans%2==1){cout<<1<<endl;return 0;}
  if(aa!=0){cout<<0<<endl;return 0;}
  ans=0;
  for(ll i=0;i<N;i++){
    vec.at(i)/=2;
    ans+=nCk(N-1,i)*vec.at(i);
  }
  if(ans%2==1){cout<<2<<endl;return 0;}
  cout<<0<<endl;return 0;
}

Measured memory_bytes: 9220
#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
 
typedef long long ll;

#define rep(i,n) for(ll i = 0; i < n; i++)

using namespace std;
 
const ll INF = ll(1e18)+1;
const double PI=3.14159265358979323846;

int main(){
  int A,B,M,a[101000]={},b[101000]={},x[101000]={},y[101000]={},c[100100]={};
  cin >> A >> B >> M;
  rep(i,A) cin >> a[i+1];
  rep(i,B) cin >> b[i+1];  
  rep(i,M) cin >> x[i] >> y[i] >> c[i];

  int ans = 1e+9;
  rep(i,M){
    ans = min(ans,a[x[i]]+b[y[i]]-c[i]);
  }
  sort(a+1,a+A+1);
  sort(b+1,b+B+1);
  ans = min(ans, a[1]+b[1]);
  cout << ans << endl;
}


Measured memory_bytes: 2176
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部変数
static FILE *szpFpI;											// 入力

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
#endif

// 出力
int
fOut(
	int piValS					// <I> 開始
	, int piValE				// <I> 終了
)
{
	int i;
	char lc1Buf[1024], lc1Out[1024];

	for (i = piValS; i <= piValE; i++) {
		sprintf(lc1Out, "%d\n", i);
#ifdef D_TEST
		fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
		if (strcmp(lc1Buf, lc1Out)) {
			siRes = -1;
		}
#else
		printf("%s", lc1Out);
#endif
	}

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 合計 - 取得
	int liSum;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &liSum);

	// 最大値
	// N(1+N)/2=S -> N=sqrt(2S-0.5*0.5)-0.5
	int liMax = (int)(sqrt(2.0 * (double)liSum - 0.5 * 0.5) - 0.5);

	while (1) {

		// 合計
		int liSum2 = liMax * (liMax + 1) / 2;

		// 差
		int liDF = liSum2 - liSum;
		if (liDF == 0) {				// なし
			fOut(1, liMax);
			break;
		}
		else if (liDF < 0) {			// 未達
			liMax++;
		}
		else {							// 達成
			fOut(1, liDF - 1);
			fOut(liDF + 1, liMax);
			break;
		}
	}

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 256
from collections import deque

k = int(input())

d = deque(list(range(1, 10)))
c = 0
v = 0
while c < k:
    v = d.popleft()
    c += 1
    if v % 10 == 9:
        d.append(v * 10 + 8)
        d.append(v * 10 + 9)
    elif v % 10 == 0:
        d.append(v * 10)
        d.append(v * 10 + 1)
    else:
        t = v % 10
        d.append(v * 10 + t - 1)
        d.append(v * 10 + t)
        d.append(v * 10 + t + 1)
print(v)



Measured memory_bytes: 40816
#include<iostream>
#include<cstring>

const int INF=1000000000;

int d[10][10];

int dyjkstra(int start,int n);

int main()
{	
	while(1)
	{
		for(int i=0;i<10;i++)
		{
			for(int j=0;j<10;j++)
			{
				d[i][j]=INF;
			}
		}

		int n,a,b,c,townnum=0;
		bool appear[10];
		memset(appear,0,sizeof(appear));
		
		std::cin>>n;
		if(n==0)break;
		
		for(int i=0;i<n;i++)
		{
			std::cin>>a>>b>>c;
			
			d[a][b]=c;
			d[b][a]=c;
			
			if(!appear[a]){appear[a]=true;townnum++;}
			if(!appear[b]){appear[b]=true;townnum++;}
		}

		int mintown,mincost=INF;
		
		for(int i=0;i<townnum;i++)
		{
			int temp;
			temp=dyjkstra(i,townnum);
			if(temp<mincost)
			{
				mintown=i;
				mincost=temp;
			}
		}
		std::cout<<mintown<<' '<<mincost<<std::endl;
	}
	return 0;
}

int dyjkstra(int start,int n)
{
	int allcost=0;//Sum of cost[i]
	int cost[10];
	bool visited[10];

	memset(visited,0,sizeof(visited));
	for(int i=0;i<n;i++)
	{
		cost[i]=INF;
	}
	
	cost[start]=0;
	while(1)
	{
		int u=-1;
		for(int i=0;i<n;i++)
		{
			if(!visited[i]&&(u==-1||cost[u]>cost[i]))//未決定で距離最小の町u
			{
				u=i;
			}
		}
		
		if(u==-1)break;
		
		visited[u]=true;
		allcost+=cost[u];
		
		
		for(int i=0;i<n;i++)//uから行ける町のcost更新	
		{
			cost[i] = cost[i]>cost[u]+d[u][i] ? cost[u]+d[u][i] : cost[i];
		}
	}
	return allcost;
}

Measured memory_bytes: 0
A,B,C,D,E,F = map(int,input().split())
concent = 0
ans = []
for one in range(F//(100*A)+1):
    for two in range((F-100*A*one)//(100*B)+1):
        for three in range((F-100*A*one-100*B*two)//C+1):
            for four in range((F-100*A*one-100*B*two-C*three)//D+1):
                water = 100*A*one+100*B*two
                sugar = C*three+D*four
                all = water + sugar
                if all == 0:
                    continue
                if E*water//100 < sugar or all > F:
                    continue
                if concent < 100*sugar/all:
                    concent = 100*sugar/all
                    ans = [all,sugar]
if len(ans) == 0:
    print(str(100*A)+' '+str(0))
else:
    print(str(ans[0])+' '+str(ans[1]))

Measured memory_bytes: 3064
# coding: utf-8

def main():
    N, M, K = map(int, input().split())

    for m in range(0, M + 1):
        d = (2 * m - M)
        if d == 0:
            n = (K + N * m - N * M)
            if n == 0:
                return "Yes"

        else:
            n = (K + N * m - N * M) / d
            if n - int(n) == 0 and n >= 0 and n <= N:
                return "Yes"
    return "No"

print(main())


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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = 1e9;
const LL LLINF = 1e18;

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

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

void solve()
{
    int N;
    cin >> N;
    LL ans = 1;

    REP0(i, N)
    {
        LL a;
        cin >> a;
        ans = lcm(a, ans);
    }

    cout << ans << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}

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

using namespace std;

using ll = long long;

bool Equal(ll n, ll b, const ll s) {
    ll sum = 0;
    while (n) {
        sum += n % b;
        n /= b;
    }
    return sum == s;
}

ll Solve() {
    ll n, s;
    cin >> n >> s;
    if (n == s) return n + 1;
    else if (n < s) return -1;
    // else if (s == 1) return n;

    for (ll b = 2; b * b <= n; ++b)
        if (Equal(n, b, s)) return b;

    ll NS = n - s, res = n + 1;
    for (ll p = 1; p * p <= NS; ++p) {
        if (NS % p != 0) continue;

        ll b1 = p + 1, b2 = NS / p + 1;
        if (2 <= b1 && Equal(n, b1, s)) res = min(res, b1);
        if (2 <= b2 && Equal(n, b2, s)) res = min(res, b2);
    }

    return (res == n + 1 ? -1 : res);
}

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

    cout << Solve() << endl;

    return 0;
}


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



typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,x,t;
    cin>>n>>x>>t;
   
   ll b2=1;
    ll i=1;
    while(i<=100000)
    {
        ll a1=x*i;
        ll b1=t*i;
        if(a1>=n)
        {
            b2=b1;
            i=i+1e18;
        }
        
        
        
       i++; 
    }
    cout<<b2;
    
    
    
    return 0;
}

Measured memory_bytes: 3644
#include<stdio.h>
#include<stdlib.h>

struct node{
  int key;
  int cst;
  struct node *next;
};

typedef struct node *gg;

gg G[10001];
gg mNode(int,int,gg);
void insert(int,int,int);

int main(){
  int i,j,n,cnt=0,v,c,c1,v1;
  int clr[10001],d[10001],pi[10001],mincst,ii;
  gg GGG;
  
  scanf("%d",&n);
  for(i=0;i<n;i++)G[i]=mNode(0,0,NULL);
  
  for(i=0;i<n;i++){
    scanf("%d%d",&v,&c);
    
    for(j=0;j<c;j++){
      scanf("%d%d",&v1,&c1);
      insert(i,v1,c1);
    }
  }
  
  for(i=0;i<n;i++){
    clr[i]=0;
    pi[i]=-1;
    d[i]=10000001;
  }
  
  d[0]=0;
  
  while(1){
    mincst=10000001;
    
    for(i=0;i<n;i++){
      if(clr[i]!=2 && d[i]<mincst){
	mincst=d[i];
	ii=i;
      }
    }
    
    if(mincst==10000001)break;
    clr[ii]=2;
    
    for(GGG=G[ii];GGG!=NULL;GGG=GGG->next){
      if(clr[GGG->key]!=2 && (GGG->cst+d[ii])<d[GGG->key]){
	pi[GGG->key]=ii;
	d[GGG->key]=GGG->cst+d[ii];
	clr[GGG->key]=1;
      }
    }
  }
  
  for(i=0;i<n;i++)printf("%d %d\n",i,d[i]);
  
  return 0;
}

gg mNode(int key,int cst,gg node){
  gg n;
  n=(gg)malloc(sizeof(struct node));
  n->key=key;
  n->cst=cst;
  n->next=node;
  return n;
}

void insert(int s,int t,int u){
  gg GGG;
  GGG=mNode(t,u,G[s]->next);
  G[s]->next=GGG;
}



Measured memory_bytes: 2080
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> v(n);
    rep(i, 0, n) {
        int a;
        cin >> a;
        rep(j, 0, a) {
            int x, y;
            cin >> x >> y;
            x--;
            v[i].push_back(make_pair(x, y));
        }
    }
    int ans = 0;
    rep(i, 0, (1 << n)) {
        bool ok = true;
        int h[n] = {};
        int cnt = 0;
        rep(j, 0, n) {
            if (i & (1 << j)) h[j] = 1;
            cnt += h[j];
        }
        rep(j, 0, n) {
            if (h[j]) {
                for (auto k : v[j]) {
                    if (h[k.first] != k.second) {
                        ok = false;
                    }
                }
            }
        }
        if (ok) ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
A, B, K = map(int, input().split(" "))
for i in range(0,K):
  if i%2 == 0:
    A -= 1 if A%2 == 1 else 0
    B += int(A/2)
    A -= int(A/2)
  else:
    B -= 1 if B%2 == 1 else 0
    A += int(B/2)
    B -= int(B/2)

print(A,B)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)
#define ALL(x) x.begin(),x.end()
/*
void solve(){
  ll n; cin >> n;
  vector<ll> prime;
  FOR(i,2,(1000006)){
    bool flg = true;
    
    if(flg) prime.push_back(i);
  }
}
*/
/*
void solve(){
  int n; cin >> n; int ans =0;
  if(n<10) {cout << n; return;}
  priority_queue<
      int,                // 要素の型はint
      std::vector<int>,   // 内部コンテナはstd::vector (デフォルトのまま)
      std::greater<int>   // 昇順 (デフォルトはstd::less<T>)
    > qb, qa;
  FOR(i,1,10000000){
    string s = std::to_string(i);
    bool flg=true;
    FOR(j,0,s.size()-1){
      if(abs(s[j]-s[j+1])>1) {flg=false; break;}
    }
    if(flg) ans++;
    if(ans==n) {cout << i; return;}
  }
  cout << ans << endl;
}*/
/*
void solve(){
  int n, k, c; cin >> n >> k >> c;
  string s; cin >> s;
}*/
template <class T> std::vector<T> divisors(const T &n) {
  std::vector<T> ret;
  T i = static_cast<T>(1);
  while (i * i < n) {
    if (n % i == static_cast<T>(0)) {
      ret.push_back(i);
      ret.push_back(n / i);
    }
    ++i;
  }
  if (i * i == n) {
    ret.push_back(i);
  }
  std::sort(ret.begin(), ret.end());
  ret.shrink_to_fit();
  return std::move(ret);
}


template<class T> struct prime{
  T N;
  vector<T> v;
  void init(const T &n){
    N = n;
    T i = static_cast<T>(2);
    while(true);
  }
};


void solve(){
  ll n; cin >> n;
  size_t ans = 0;
  for (const ll k : divisors(n)) {
    if (k == 1)
      continue;
    ll m = n;
    while (m % k == 0) {
      m /= k;
    }
    if (m % k == 1) {
      ans += 1;
    }
  }
  ans += divisors(n - 1).size();
  std::cout << ans - 1 << std::endl;
}

void solve2(){
  int n, k, c;
  scanf("%d%d%d",&n,&k,&c);
  char *s;
  s = new char[n+10];
  scanf("%s",s);
  vector<int> L(k+5), R(k+5);
  int cnt = 0, bf=-987654321;
  FOR(i,0,n){
    if(s[i]=='o' && (i-bf)>c) {bf = i; L[cnt] = i; cnt++;}
    if(cnt==k) break;
  }
  bf = 987654321; cnt = k-1;
  IFOR(i,0,n){
    if(s[i]=='o' && (bf-i)>c) {bf = i; R[cnt] = i; cnt--;}
    if(cnt==-1) break;
  }
  FOR(i,0,k){
    if(L[i]==R[i])  cout << (L[i]+1) << endl ;
  }
}

int main(){
  //solve();
  solve2();
  return 0;
}

Measured memory_bytes: 3200
import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
  x, y = map(int,input().split())
  g[x-1].append(y-1)
#print(g)
mem = [-1]*n

def dfs(v):
  if mem[v] != -1:
    return mem[v]
  mem[v] = r = max(dfs(w) for w in g[v]) +1 if g[v] else 0
  return r
print(max(dfs(t) for t in range(n)))


Measured memory_bytes: 106648
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 4000000;
const int mod = 998244353;
int a[N];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("input.txt", "r", stdin);
    int n, k;
    cin >> n >> k;
    n %= k;
    int ans = n;
    for (int i = 0; i < 100; i++){
        n = abs(n - k);
        ans = min(ans, n);
    }
    cout << ans;
}


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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const double INF = 1e18;
const LL MOD = 1e9+7;

struct C{
  double x, y, r;
  C(double x=0,double y=0, double r=0):x(x),y(y),r(r)
  {}
};

double dist(C& c1, C& c2){
  double dx = c1.x - c2.x;
  double dy = c1.y - c2.y;
  if(dx*dx + dy*dy <= (c1.r+c2.r)*(c1.r+c2.r))
	return 0.;
  return sqrt((dx*dx + dy*dy)) - sqrt((c1.r+c2.r)*(c1.r+c2.r));
}

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

  C s, t;
  cin >> s.x >> s.y >> t.x >> t.y;
  int N; cin >> N;
  vector<C> cs;
  cs.PB(s);
  REP(i,N){
	C c;
	cin >> c.x >> c.y >> c.r;
	cs.EB(c);
  }
  cs.PB(t);

  vector<vector<double>> ds(N+2, vector<double>(N+2));
  REP(i,N+2) REP(j,i+1){
	ds[i][j] = ds[j][i] = dist(cs[i], cs[j]);
  }

  using Type = pair<double,int>;
  vector<double> d(N+2, INF);
  priority_queue<Type, vector<Type>, greater<Type> > pq;
  fill(d.begin(), d.end(), INF);
  d[0] = 0;
  pq.push(MP(0,0));

  while(!pq.empty()){
	Type pii = pq.top(); pq.pop();
	int v = pii.second;
	if(d[v] < pii.first) continue;
	REP(i,N+2){
	  if(d[i] > d[v] + ds[i][v]){
		d[i] = d[v] + ds[i][v];
		pq.push(Type(d[i], i));
	  }
	}
  }

  cout << fixed << setprecision(10) <<  d[N+1] << endl;

  return 0;
}


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

struct Tree {
    struct Node {
        int value;
        Node *left;
        Node *right;
    };

    vector<Node> nodes;
    int size;

    vector<int> order;

    Tree() : size(0), nodes(500000) {
    }

    Node CreateNode(int value) {
        Node me;
        me.value = value;
        me.left = nullptr;
        me.right = nullptr;
        return me;
    }

    void Insert(int value) {
        if(size == 0) {
            nodes[size++] = CreateNode(value);
        }
        else {
            nodes[size] = CreateNode(value);
            Node *me  = &nodes[size];
            ++size;

            Node *cur = &nodes[0];
            while(true) {
                if(value < cur->value) {
                    if(cur->left == nullptr) {
                        cur->left = me;
                        break;
                    }
                    else {
                        cur = cur->left;
                    }
                }
                else if (value > cur->value) {
                    if(cur->right == nullptr) {
                        cur->right = me;
                        break;
                    }
                    else {
                        cur = cur->right;
                    }
                }
                else {
                    cerr << "conflict occured" << endl;
                    abort();
                }
            }
        }
    }  // void Insert(int value)

    void ShowWithInorderWalk() {
        if(size == 0) return;
        order.clear();
        ShowWithInorderWalkInner(&nodes[0]);
    }

    void ShowWithInorderWalkInner(const Node *cur) {
        if(cur->left != nullptr) ShowWithInorderWalkInner(cur->left);
        order.push_back(cur->value);
        if(cur->right != nullptr) ShowWithInorderWalkInner(cur->right);
    }

    void ShowWithPreorderWalk() {
        if(size == 0) return;
        order.clear();
        ShowWithPreorderWalkInner(&nodes[0]);
    }

    void ShowWithPreorderWalkInner(const Node *cur) {
        order.push_back(cur->value);
        if(cur->left != nullptr) ShowWithPreorderWalkInner(cur->left);
        if(cur->right != nullptr) ShowWithPreorderWalkInner(cur->right);
    }
};

int main() {
    Tree tree;
    int N; cin >> N;
    while(N--) {
        string cmd;
        cin >> cmd;
        if(cmd == "print") {
            tree.ShowWithInorderWalk();
            for(int item : tree.order) {
                cout << ' ' << item;
            }
            cout << endl;
            tree.ShowWithPreorderWalk();
            for(int item : tree.order) {
                cout << ' ' << item;
            }
            cout << endl;
        }
        else {
            int value; cin >> value;
            tree.Insert(value);
        }
    }
}

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

int main(){
  long long K,A,B;
  cin >> K >> A >> B;
  long long bis=1;
  bool mon=false;
  for(int i=0;i<K-1;i++){
    if(mon){mon=false; bis+=B;}
    else if(bis>=A){bis-=A; mon=true;}
    else{bis++;}
  }
  if(mon){mon=false; bis+=B;}
  else{bis++;}
  bis=max(bis,K+1);
  cout << bis << endl;
}

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

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int n,m;
struct uzi
{
    int a,b;
}p[N];
vector<int>v[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b,v[p[i].a].pb(p[i].b);
    LL ans=0;
    int now=0;
    priority_queue<int>q;
    for(int i=m;i>=1;i--){
        ++now;
        // cout<<i<<endl;
        for(auto k:v[now]){
            q.push(k);
        }
        if(q.empty())continue;
        ans+=q.top();
        q.pop();
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 9472
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>

using namespace std;
typedef long long ll;

int main()
{

    ll n;
    cin >> n;

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

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

    ll c[n - 1];
    for (int i = 0; i < (n - 1); i++)
    {
        cin >> c[i];
    }

    int sum = 0;
    int previous = 100;
    for (int i = 0; i < n; i++)
    {
        sum += b[a[i] - 1];

        if (a[i] - previous == 1)
        {
            sum += c[a[i] - 2];
        }

        previous = a[i];
    }

    // sort(b, b + a);

    // for (int i = 0; i < (a - 1); i++)
    // {
    //     b[i + 1] = (b[i] + b[i + 1]) / 2;
    // }

    // // cout << fixed;
    // // cout << setprecision(14);
    cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
int main(){
    string as,bs,u;
    int a,b;
    cin>>as>>bs>>a>>b>>u;
    if(as.compare(u)==0) a--;
    else b--;
    cout<<a<<" "<<b<<endl;

}

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

signed main(){
	string  s1, s2, s3;
	char d = 'A' - 'a';
	cin >> s1 >> s2 >> s3;
	printf("%c%c%c\n", s1[0] + d, s2[0] + d, s3[0] + d);
	return 0;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

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


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


using namespace std;

#define ll long long

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   int k;
   cin >> k;
   ll ans=0;
   for(int i=1;i<=k;i++) {
	   for(int j=1;j<=k;j++) {
		   for(int ij=1;ij<=k;ij++) {
			   ans+=__gcd(__gcd(i,j),ij);
		   }
	   }
   }
   cout << ans;
   return 0;
}




Measured memory_bytes: 3604
// 2012/12/10 Tazoe

#include <iostream>
using namespace std;

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

if(N==0&&M==0)
break;

	int S[1001];
	for(int i=1; i<=N; i++){
		cin >> S[i];
	}

	int D[1001];
	for(int i=1; i<=M; i++){
		cin >> D[i];
	}

	int P = 1;
	int I = 1;
	for(; I<=M; I++){
		P += D[I];
		if(P>=N)
			break;

		P += S[P];
		if(P>=N)
			break;
	}

	cout << I << '\n';
}

	return 0;
}

Measured memory_bytes: 1168
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

int fun(char c,char cc){
    return (c=='.' and cc=='#');
}

int dp[101][101];
inline void solve(){
    int h,w; 
    cin>>h>>w; 
    string s[h]; 
    for (int i=0;i<h;i++) cin>>s[i]; 
    for (int i=0;i<h;i++){ 
        for (int j=0;j<w;j++){ 
            dp[i][j]=100000000;
        }
    }
    dp[0][0] = ((s[0][0]=='#')?1:0); 
    for (int i=0;i<h;i++){ 
        for (int j=0;j<w;j++){ 
            if (j!=0) dp[i][j]=min(dp[i][j],dp[i][j-1]+fun(s[i][j-1],s[i][j])); 
            if (i!=0) dp[i][j]=min(dp[i][j],dp[i-1][j]+fun(s[i-1][j],s[i][j])); 
        } 
    } 
    cout << dp[h-1][w-1] << endl; 
}

signed main() 
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3656
N, A = map(int, input().split())
X = list(map(int, input().split()))
Y = [x - A for x in X]

dp = [0] * 5010
dp[2500] = 1

for y in Y:
    r = []
    if y >= 0:
        r = range(5009, -1, -1)
    else:
        r = range(5010)
    for i in r:
        if i - y < 0 or i - y >= 5010:
            continue
        dp[i] += dp[i - y]
print(dp[2500] - 1)


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

using namespace std;

#define MAX 300001
 
bool check[MAX];
 
void print(int n){
    cout << n << ": ";
}
 
void init(){
    fill(check,check+MAX,false);
}
 
int main(){
    int n;
     
    while(cin >> n , n != 1){
        vector<int> v;
        init();
        print(n);
         
        for(int i = 2 ; i <= n ; i++){
            if(n%i==0&&(i%7==1||i%7==6)){
		for(int j = 2*i ; j <= n ; j+=i) check[j] = true;
		if(!check[i]) v.push_back(i);
            }
        }
        for(int i = 0 ; i < v.size() ; i++){
            if(!i) cout << v[i];
            else cout << ' ' << v[i];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3412
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
int main(){
    string s;
    int n;
    cin>>n>>s;
    REP(i,s.length()){
        if(s[i]+n>'Z'){
            s[i]='A'-1+s[i]+n-'Z';
        }
        else s[i]=s[i]+n;
    }
    cout<<s<<endl;
}

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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int test=0;
    for(int i=0;i<n;i++)
    {
        if (a[i]%2==0)
        {
           if ((a[i]%3!=0)and(a[i]%5!=0))
           {
               test=1;
               break;
           }
        }
    }
    if (test==1)
        cout<<"DENIED";
    else
        cout<<"APPROVED";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define dump(x) cout << #x << " = " << (x) << endl;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define int long long

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  vector<int> V(N);
  REP(i, N) cin >> V[i];

  int ans = 0;
  // i: 操作を行う回数
  for(int i = 1; i <= K && i <= N; i++) {
    // l: 左から取り出す回数 r: 右から取り出す回数
    for(int l = 0; l <= i; l++) {
      // que: 取り出した宝石を入れる小さい順のpriority_que
      priority_queue<int, vector<int>, greater<int>> que;
      int r = i - l;
      for(int x = 0; x < l; x++) {
        que.push(V[x]);
      }
      for(int y = 0; y < r; y++) {
        que.push(V[N - 1 - y]);
      }
      // modosu:カードを戻せる回数
      int modosu = K - i;
      // queから負の要素を取り出して戻す
      while(que.top() < 0 && modosu > 0 && que.size() > 0) {
        que.pop();
        modosu--;
      }
      // tmp: que中の要素の価値の合計
      int tmp = 0;
      while(que.size()) {
        tmp += que.top();
        que.pop();
      }
      ans = max(tmp, ans);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    //freopen("t5.in","r",stdin);
   //freopen("t5.out","w",stdout);
    int i,j,n,m;
    long long a,b,c;
    cin>>a>>b>>c;
    long long daan=b*(a/(b+c));
    a%=(b+c);
    daan+=min(a,b);
    cout<<daan<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO 自動生成されたメソッド・スタブ

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] V = new int[N];
        int[] C = new int[N];
        int[] difference = new int[N];
        int max = 0;

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

            V[i] = sc.nextInt();
        }

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

            C[i] = sc.nextInt();
        }

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

            difference[i] = V[i]-C[i];

            if( difference[i] > 0 ) {

                max += difference[i];
            }
        }

        System.out.println(max);

        sc.close();
    }
}

Measured memory_bytes: 21716
#include<stdio.h>
#include<string.h>

int main(){
  char str_1[100],str_2[100];
  int n,i,result,T = 0,H = 0;

  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf("%s %s",str_1,str_2);
	result = strcmp(str_1,str_2);
	
	if(result == 0){
	  T += 1;
	  H += 1;
	}else if(result > 0){
	  T += 3;
    }else if(result < 0){ 
	  H += 3;
	}
  }
  printf("%d %d\n",T,H);
  
  return 0;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll x,y,z,k; cin>>x>>y>>z>>k;
  vll a(x) , b(y), c(z);
  rep(i,x) cin>>a[i];
  rep(i,y) cin>>b[i];
  rep(i,z) cin>>c[i];
  
  vll ab, bc, ca;
  rep(i,x) rep(j,y) ab.push_back(a[i]+b[j]);
  rep(i,y) rep(j,z) bc.push_back(b[i]+c[j]);
  rep(i,z) rep(j,x) ca.push_back(c[i]+a[j]);
  
  sort(ab.rbegin(),ab.rend());
  sort(bc.rbegin(),bc.rend());
  sort(ca.rbegin(),ca.rend());
  
  // 合計値、自分、自分の値、自分以外の次のカーソル
  priority_queue<tuple<ll,ll,ll,ll>> q;
  rep(i,x) {
    q.push(tuple<ll,ll,ll,ll>(a[i]+bc[0], 0, a[i], 0));
  }
  rep(i,y) {
    q.push(tuple<ll,ll,ll,ll>(b[i]+ca[0], 1, b[i], 0));
  }
  rep(i,z) {
    q.push(tuple<ll,ll,ll,ll>(c[i]+ab[0], 2, c[i], 0));
  }
  
  ll cnt=0;
  vll ans;
  while(!q.empty() && cnt<=k*3){
    ll sum, self, point, pos;
    tie(sum,self,point,pos)=q.top(); q.pop();
    // cout<<sum<<' '<<self<<' '<<point<<' '<<pos<<endl;
    
    ans.push_back(sum);
    cnt++;
    if(self==0){
      if(pos+1<bc.size()){
        q.push(tuple<ll,ll,ll,ll>(point+bc[pos+1], self, point, pos+1));
      }
    }
    if(self==1){
      if(pos+1<ca.size()){
        q.push(tuple<ll,ll,ll,ll>(point+ca[pos+1], self, point, pos+1));
      }
    }
    if(self==2){
      if(pos+1<ab.size()){
        q.push(tuple<ll,ll,ll,ll>(point+ab[pos+1], self, point, pos+1));
      }
    }
  }
  
  rep(i,k*3){
    if(i%3==0) cout<<ans[i]<<endl;
  }
  
}

Measured memory_bytes: 31268