akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define SORT(v) sort(ALL(v))
//#define scanf scanf_s
typedef pair<int, int> P;

int n, m;
string s;
int a[100005];
int b[100005];
int c[10005];
set<int> used;

char sima[55][55];
int cntw, cntb, cnttmp;
char tmp;
int di[] = { -1, 0, 0, 1 }; int dj[] = { 0, -1, 1, 0 };
int h, w;
void search(int i,int j)
{
	if (i < 0 || i >= h || j < 0 || j >= w) return;
	if (sima[i][j] == 'W')
	{
		if (tmp == 'B')
		{
			cnttmp = -10000000;
		}
		else tmp = 'W';
	}
	if (sima[i][j] == 'B')
	{
		if (tmp == 'W')
		{
			cnttmp = -10000000;
		}
		else tmp = 'B';
	}
	if (sima[i][j] == '.')
	{
		sima[i][j] = '@';
		cnttmp++;
		REP(k, 4) search(i + di[k], j + dj[k]);
	}
}

int main()
{
	while (cin >> w >> h, w)
	{
		REP(i, h)REP(j, w) cin >> sima[i][j];
		cntw = 0, cntb = 0;
		REP(i, h)REP(j, w)
		{
			cnttmp = 0;
			tmp = '@';
			if (sima[i][j] == '.')
			{
				search(i, j);
				if (cnttmp>0&&tmp == 'B') cntb += cnttmp;
				if (cnttmp>0&&tmp == 'W') cntw += cnttmp;
			}
		}
		cout << cntb << " " << cntw << endl;
	}
	return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
#define FOR(i, a, b) for(LL i=(LL)(a);i<(LL)(b);i++)
#define REP(i,x) for(LL i=0;i<(LL)(x);i++)

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

    LL N, A, B;
    cin >> N >> A >> B;

    // フェイルセーフ
    if(A == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    if(B == 0)
    {
        cout << N << endl;
        return 0;
    }

    LL shou = N / (A + B);

    LL amari = N % (A + B);

    if(amari <= A)
    {
        cout << shou * A + amari << endl;
    }
    else
    {
        cout << (shou + 1) * A << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
const ll MOD=1000000007;
const ll INF=1000000000;

int main(){
    int N;
    cin >> N;
    vector<ll> a(N);
    bool ans0=true;
    rep (i,N){
        cin >> a[i];
        if (a[i]!=0){
            ans0=false;
        }
    }
    if (ans0){
        cout << "Yes" << endl;
    }
    else {
        bool ans=true;
        if (N%3!=0){
            ans=false;
        }
        else {
            map<ll,int> m;
            int n=N/3;
            rep (i,N){
                m[a[i]]++;
            }
            if (m.size()==3){
                vector<int> b(3);
                int cnt=0;
                for (auto x:m){
                    if (x.second!=n){
                        ans=false;
                        break;
                    }
                    else {
                        b[cnt]=x.first;
                        cnt++;
                    }
                }
                int x=b[0]^b[1],y=b[1]^b[2],z=b[2]^b[0];
                if (x!=b[2]||y!=b[0]||z!=b[1]){
                    ans=false;
                }
            }
            else if (m.size()==2){
                vector<Pii> v(2);
                int cnt=0;
                for (auto x:m){
                    v[cnt]=Pii(x.first,x.second);
                    cnt++;
                }
                if (!((v[0].first==0&&v[0].second==n)||(v[1].first==0&&v[1].second==n))){
                    ans=false;
                }
            }
            else {
                ans=false;
            }
        }
        if (ans){
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 5632
#include<iostream>

using namespace std;

int main()
{
	char *week[7]={ "Thursday",
					"Friday",
					"Saturday",
					"Sunday",
					"Monday",
					"Tuesday",
					"Wednesday"};
	int mouse[12]={31,29,31,30,31,30,31,31,30,31,30,31};
	int tuki,day;

	while(cin>>tuki>>day,tuki,day){
		int now=0;
		now+=day-1;
		for(tuki=tuki-2;tuki>=0;tuki--)
			now+=mouse[tuki];
		cout<<week[now%7]<<endl;
	}

	return 0;
}

Measured memory_bytes: 1156
/*
No i'm not down, No I'm not out
*/
#include <bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll  long long
#define f(i,a,b) for(int i=a; i<b; i++)
#define pb push_back
#define MP make_pair
#define vi vector<int>
#define vll vector<long long>
#define M map<int,int>
#define F     first
#define S    second
#define nl "\n"
#define lb lower_bound
#define ub upper_bound
#define max(a, b) (a < b ? b : a)
#define min(a, b) (a > b ? b : a)
#define mem(a,n)  memset(a, n, sizeof(a))
#define all(v) v.begin(), v.end()
int dx[8] ={0, 0, 1, 1, 1, -1, -1, -1};
int dy[8] ={1, -1, -1, 0, 1, -1, 0, 1};
#define mod 1000000007
#define N 100005

int add(int a, int b)
{
    return ((a % mod) + (b % mod)) % mod;
}

using namespace std;

int main()
{
    fast();
    int n;
    cin >> n;
    double dp[n+1] = {}, curr[n+1] = {},sum = 0, p[n+1];
    f(i, 1, n+1)cin >> p[i];
    f(i, 1, n+1)
    {
        f(j, 1, i+1)
        {
            if(i == 1)curr[j] = p[i];
            else curr[j] = dp[j-1] * p[i] + dp[j] * (1.0 - p[i]);
            // cout << i << " " << j << " " << p[i] << " " << dp[j] << " " << curr[j] << nl;
            sum += curr[j];
        }
        curr[0] = 1 - sum;
        sum = 0;
        f(j, 0, n+1)dp[j] = curr[j];
    }
    f(j, n / 2 + 1, n+1)sum += dp[j];
    cout << setprecision(10) << fixed << sum;
}

Measured memory_bytes: 384
#include<stdio.h>
char str[10000];
int main() {
  int i, j;
  while (fgets(str, 10000, stdin) != NULL) {
    for (i = 0; i < 26; i ++) {
      for (j = 0; j < 10000; j ++) {
	if ('a' <= str[j] && str[j] <= 'z') str[j] = (str[j] - 'a' + 1) % 26 + 'a';
      }
      for (j = 0; j < 9997; j ++) {
	if (str[j] == 't' && str[j + 1] == 'h'  && ((str[j + 2] == 'e' && str[j + 3] == ' ') || (str[j + 2] == 'i' && str[j + 3] == 's' && str[j + 4] == ' ') || (str[j + 2] == 'a' && str[j + 3] == 't' && str[j + 4] == ' '))) {
	  printf("%s", str);
	  break;
	}
      }
    }
    for (i = 0; i < 10000; i ++) str[i] = 0;
  }
  return 0;
}

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

int main() {
	int N, A, T;
  	int H[1010];
  
  	cin >> N >> T >> A;
  	for (int i=0; i<N; i++) cin >> H[i];
  
  	double min = 1000000.0;
  	int place = 0;
  
  	for (int i=0; i<N; i++) {
      	double gap, ave;
      	ave = T - (0.006 * H[i]);
      	gap = abs(A - ave);
      	if (gap < min) {
        	min = gap;
          	place = i+1;
        }
    }
  	cout << place << endl;
}

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

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

using namespace std;

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

vector<vector<int>> G;
vector<vector<int>> dist;
vector<int> ress;

void bfs(int t) {
  queue<int> que;
  que.push(t);
  dist[t][t] = 0;
  while (!que.empty()) {
    int cur = que.front();
    que.pop();
    for (int node : G[cur]) {
      if (dist[t][node] != -1) {
        continue;
      }
      dist[t][node] = dist[t][cur] + 1;
      ress[dist[t][node] - 1]++;
      que.push(node);
    }
  }
}

int main() {
  int n, x, y;
  cin >> n >> x >> y;
  G = vector<vector<int>>(n, vector<int>());
  dist = vector<vector<int>>(n, vector<int>(n, -1));
  ress = vector<int>(n);
  rep(i, n) {
    int cur = i;
    if (cur != n - 1) {
      G[cur].push_back(cur + 1);
      G[cur + 1].push_back(cur);
    }
  }
  G[x - 1].push_back(y - 1);
  G[y - 1].push_back(x - 1);

  // 距離の計算
  dist = vector<vector<int>>(n, vector<int>(n, -1));
  rep(i, n) {
    bfs(i);
  }

  // 出力
  rep(i, n - 1) {
    int res = ress[i];
//    rep(j, n) {
//      for (int k = j + 1; k < (n); ++k) {
//        if (dist[j][k] == i + 1) {
//          res++;
//        }
//      }
//    }
    cout << res / 2 << endl;
  }

  return 0;
}


Measured memory_bytes: 31744
module.exports=function(t){var e={};function n(r){if(e[r])return e[r].exports;var i=e[r]={i:r,l:!1,exports:{}};return t[r].call(i.exports,i,i.exports,n),i.l=!0,i.exports}return n.m=t,n.c=e,n.d=function(t,e,r){n.o(t,e)||Object.defineProperty(t,e,{enumerable:!0,get:r})},n.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},n.t=function(t,e){if(1&e&&(t=n(t)),8&e)return t;if(4&e&&"object"==typeof t&&t&&t.__esModule)return t;var r=Object.create(null);if(n.r(r),Object.defineProperty(r,"default",{enumerable:!0,value:t}),2&e&&"string"!=typeof t)for(var i in t)n.d(r,i,function(e){return t[e]}.bind(null,i));return r},n.n=function(t){var e=t&&t.__esModule?function(){return t.default}:function(){return t};return n.d(e,"a",e),e},n.o=function(t,e){return Object.prototype.hasOwnProperty.call(t,e)},n.p="",n(n.s=0)}([function(t,e,n){"use strict";var r=n(1);n(2)(r.readFileSync("/dev/stdin","utf8"))},function(t,e){t.exports=require("fs")},function(t,e,n){"use strict";var r=n(3),i=n(5);t.exports=function(t){var e=new r(t);i(e)}},function(t,e,n){"use strict";var r=n(4);t.exports=class{constructor(t){var e=t.trim().split(/\s+/g);this.inp=new r(e)}inr(){return this.inp.deq()}in(){return parseInt(this.inp.deq(),10)}fin(){this.inp.clear()}}},function(t,e,n){"use strict";t.exports=class{constructor(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:[];this.size=t.length,this.items=t,this.ind=0}enq(t){this.size+=1,this.items.push(t)}deq(){var t=this.items[this.ind];return this.size-=1,this.ind+=1,t}clear(){this.items=[],this.size=0,this.ind=0}}},function(t,e,n){"use strict";t.exports=function(t){for(var e=t.in(),n=t.inr(),r=1,i=1;i<e;i++)n[i]!=n[i-1]&&r++;console.log(r)}}]);

Measured memory_bytes: 21192
#include <stdio.h>
int main(void){
  int a,b,c,tmp;
  
  scanf("%d %d %d",&a,&b,&c);
  
  if(a>b){
    tmp=a;
  	a=b;
  	b=tmp;
  }
  if(b>c){
    tmp=b;
  	b=c;
  	c=tmp;
  }
  if(a>b){
    tmp=a;
  	a=b;
  	b=tmp;
  }
	printf("%d %d %d\n",a,b,c);
  return 0;
}

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

int main(){
	int a,b,c,d,e;
	while(cin >> a >> b >> c >> d >> e && a ){
		a--,b--,c--,d--,e--;
		set<int> v;
		v.insert(a);
		v.insert(b);
		v.insert(c);
		v.insert(d);
		v.insert(e);
		if( v.size() == 3 || v.size() == 1){
			for(int i = 0 ; i < 5 ; i++)
			 cout << 3 << endl;
		}else{
			set<int>::iterator it = v.begin();
			set<int>::iterator it2 = it;
			it++;
			int W[3] = {};
			if( (*it2) == ((*it)+1)%3 ){
				W[*it] = 1;
				W[*it2] = 2;
			}else{
				W[*it] = 2;
				W[*it2] = 1;
			}
			cout << W[a] << endl;
			cout << W[b] << endl;
			cout << W[c] << endl;
			cout << W[d] << endl;
			cout << W[e] << endl;
		}
	}
}

Measured memory_bytes: 0
#include <stdio.h>
int main(){
  int M[101][101];
  int n,u,k,v,i,j;
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=0;
    }
  }
  
  for(i=0;i<n;i++){
    scanf("%d",&u);
    scanf("%d",&k);
    u--;
    for(j=0;j<k;j++){
      scanf("%d",&v);
      v--;
      M[u][v]=1;
    }
  }
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j>0){
	printf(" ");
      }
      printf("%d",M[i][j]);
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 640
fun main(args: Array<String>) {
    val (n,m)= readLine()!!.split(" ").map { it.toInt() }
    val dp = IntArray(n+2)
    dp[0] = 1
    val broken = (1..m).map { readLine()!!.toInt() }.toSet()

    (0..n-1).forEach { i ->
        dp[i+1] += if((i+1) in broken) 0 else dp[i]
        dp[i+2] += if((i+2) in broken) 0 else dp[i]
        dp[i+1] %= 1000000007
        dp[i+2] %= 1000000007
    }
    println(dp[n])
}

Measured memory_bytes: 48592
K = int(input())
A = list(map(int, input().split()))[::-1]
if A[0] != 2:
  print(-1)
  quit()

left = 2; right = 3
for a in A[1:]:
  ra = right - right%a
  if ra < left:
    print(-1)
    quit()
  l1 = ra; r1 = ra + a - 1
  la = left + (a - (left%a))%a
  l2 = la; r2 = la + a - 1
  left = min(l1, l2)
  right = max(r1, r2)

print(left, right)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
int main()
{
  int N;
  cin >> N;
  vector<ll>cnt(100100,0);
  rep(i,N){
    int a;
    cin >> a;
    cnt[a]++;
  }
  ll ans=0;
  for(int i=0;i<=100010;i++){
    ll sum=0;
    if(i-1>=0)sum+=cnt[i-1];
    sum+=cnt[i];
    if(i+1<100100)sum+=cnt[i+1];
    ans=max(ans,sum);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <string>

int main()
{
	std::string ln;
	std::getline(std::cin, ln);

	for (std::string::iterator iR = ln.begin(), RiL, LiR; iR != ln.end(); iR = LiR) {
		RiL = std::find( iR, ln.end(), 'L');
		LiR = std::find(RiL, ln.end(), 'R');

		int R = RiL -  iR;
		int L = LiR - RiL;

		int RtoL = L&1;
		int LtoR = R&1;

		for (int i = 1; i < R; ++i) {
			std::cout << 0 << ' ';
		}
		std::cout << (R/2 + L/2 + LtoR) << ' ' << (R/2 + L/2 + RtoL) << ' ';
		for (int i = 1; i < L; ++i) {
			std::cout << 0 << ' ';
		}
	}

	std::cout << std::endl;
	return 0;
}


Measured memory_bytes: 640
# -*- coding: utf-8 -*-

N = int(input())

D, X = map(int, input().split())
A = [int(input()) for _ in range(N)]

count = []
for i in range(N):
    cnt = 0
    for d in range(D):
        if A[i]*d + 1 <= D:
            cnt += 1
        else:
            break
    count.append(cnt)

print(sum(count) + X)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
using namespace std;
#define i64  long long
//  #define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define MOD 1000000007


void solve()
{
  
  map<string,int> mp;
  int N;
  cin>>N;
  for (int i = 0; i < N; i++)
  {
    string str;
    string A;
    cin>>str;
    cin>>A;
    if(str == "insert")
    {
      mp[A]++;
    }
    else //find
    {
      if(mp[A]>0)
      {
        cout<<"yes"<<endl;
      }
      else
      {
        cout<<"no"<<endl;
      }
    }
    
  }
  
  
  return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  solve();
 
  return 0;
}


Measured memory_bytes: 47512
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b,densha=0;
  cin>>n>>a>>b;
  densha=n*a;
  if(densha>=b)cout<<b<<endl;
  else if (densha<=b)cout<<densha<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long int ll ;

ll max(ll a , ll b)
{
  return (a > b) ? a: b;
}
ll min(ll a , ll b)
{
  return (a < b) ? a : b;
}
void memset(int *arr , int n , int value)
{
    for(int i= 0; i<n ; i++)
    {
        arr[i] = value;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     int n;
    cin>>n;
    int *arr = new int[n];
    for(int i=0; i<n; i++)
    {
        cin>>arr[i];
    }
    int *dp = new int[n+1];
    memset(dp , n+1 , 0) ;
    dp[0] = 0;
    dp[1] = abs(arr[1] - arr[0]) ;
    for(int i= 2; i< n ; i++)
    {
        int one = abs(arr[i] - arr[i-1]) ;
        int two = abs(arr[i] - arr[i-2]) ;
        dp[i] = min(dp[i-1] + one , dp[i-2] + two);
    }
    cout<<dp[n-1] ;
    return 0;
}


Measured memory_bytes: 1024
import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())

num = collections.Counter(A)

S = sum(A)
slist = []

for i in range(Q):
	B, C = map(int, input().split())
	numb = num[B]
	S += (C - B) * numb
	num[C] += numb
	num[B] = 0
	slist.append(S)

[print(i) for i in slist]

Measured memory_bytes: 27164
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <cmath>
using namespace std;

int main(void){
  int L,R,d;
  int count = 0;
  cin >> L >> R >> d;
  for(int i=L;i<=R;i++){
    if(i%d==0) count++;
  }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 3756
is_prime = ->(n) {
  return false if n < 2
  return true if n == 2 or n == 3
  return false if (n % 2).zero? or (n % 3).zero?
  k, step = 5, 2
  guard = Math.sqrt(n).to_i
  while k <= guard
    return false if (n % k).zero?
    k += step
    step = 6 - step
  end
  true
}

n = gets.to_i
co = 0
$stdin.readlines.map(&:to_i).each {|num| co += 1 if is_prime.(num)}
puts co



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

int main() {
	long long A, B, X;
	cin >> A >> B >> X;
	if (A <= X) X -= A, A = 0;
	else A -= X, X = 0;
	if (B <= X) X -= B, B = 0;
	else B -= X, X = 0;
	cout << A << " " << B << endl;
}

Measured memory_bytes: 256
import sys
from collections import Counter
from collections import deque
import math
import fractions
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=lmp()



a4=0
a0=0
a2=0
for i in range(n):
    if a[i]%4==0:
        a4+=1
    elif a[i]%4==1 or a[i]%4==3:
        a0+=1
    else:
        a2+=1

if a2==0 and a4>=a0-1:
    print("Yes")
    exit()
if a4>=a0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 16300
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        s: String,
    }
    let pattern = ["eraser", "erase", "dreamer", "dream"];
    let ans = pattern.iter().fold(s, |acc, x| acc.replace(x, ""));
    println!("{}", if ans == "" {"YES"} else {"NO"});
}


Measured memory_bytes: 4352
import scala.io.StdIn
import scala.collection.mutable.ListBuffer

object Main extends App {
  val out = new java.io.PrintWriter(System.out)
  val n = StdIn.readInt
  val a = StdIn.readLine.split(" ").map(_.toInt)

  def fe(b:ListBuffer[Int], cnt:Int, num:Int):Unit = {
      if((cnt&1) == 0) num +=: b else b += num
  }
  def fo(b:ListBuffer[Int], cnt:Int, num:Int):Unit = {
      if((cnt&1)==0) b += num else num +=: b
  }

  val b = ListBuffer.empty[Int]
  val len = a.size
  if((len&1) == 0) a./:(1)((cnt,i) => {fe(b,cnt,i); cnt+1})
  else  a./:(1)((cnt,i) => {fo(b,cnt,i); cnt+1})

  out.println(b.mkString(" "))
  out.flush
}

Measured memory_bytes: 79920
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
        long n, k;
        scanf("%ld%ld", &n, &k);

        std::vector<long> ins_nums;
        long op_nums[100001];
        long a, op_num;

        for (long i=0; i<100001; ++i) {
                op_nums[i] = 0;
        }

        for (long i=0; i<n; ++i) {
                scanf("%ld%ld", &a, &op_num);
                ins_nums.push_back(a);
                op_nums[a] += op_num;
        }
        sort(ins_nums.begin(), ins_nums.end());
        std::vector<long>::iterator end;
        end = unique(ins_nums.begin(), ins_nums.end());
        ins_nums.erase(end, ins_nums.end());

        for (size_t i=0; i<ins_nums.size(); ++i) {
                k = k - op_nums[ins_nums[i]];
                if (k<=0) {
                        printf("%ld\n", ins_nums[i]);
                        break;
                }
        }

        return 0;
}

// 1.vector 的添加方式 push_back
// 2.对测试数据的 case 想的不全


Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 99999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl
#define Vecpr(K,L1,L2,N) vector<pair<L1,L2>> K(N)
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,R) vector<vector<L>> K(N, vector<L>(M,R))
#define pint pair<int,int>
#define Lower(v,X) lower_bound(v.begin(),v.end(),X)-v.begin();
#define mod 1000000007
#define MAX 5100000
#define ceili(x,y) (x+y-1)/y  
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
  lli A,B,C,D,E,L,R,X,Y,W,H,N,M,K,sum=0,num=0,flag=0;string S,T;
  cin >> N;
  vector<vector<pint>>Graph(N);
  Vec(dist,lli,N,0);
  Vec(Color,int,N,0);
  rep(i,0,N-1){
    cin >> A >> B >> C;
    A--;B--;
    Graph[A].pb(pint(B,C%2));
    Graph[B].pb(pint(A,C%2));
  }
  queue<pint> que;
  que.push(pint(0,0));
  dist[0]=1;
  while(!que.empty()){
    auto Xq=que.front();que.pop();
    int pr=Xq.first;
    int pc=Xq.second;
    rep(i,0,Graph[pr].size()){
      int next=Graph[pr][i].first;
      int dt=Graph[pr][i].second;
      if(dist[next])continue;
      dist[next]=1;
      que.push(pint(next,pc^dt));//偶奇判定 1^1=0,1^0=1;
      Color[next]=pc^dt;
  }
  }
  rep(i,0,N)Out(Color[i]);
  }



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

void replace(string& str) {
    for (int i = 0; i < (int)str.length() - 4; i++) {
        string sub = str.substr(i, 5);
        if (sub == "apple") {
            str.replace(i, 5, "peach");
            i += 4;
        } else if (sub == "peach") {
            str.replace(i, 5, "apple");
            i += 4;
        }
    }
}

int main() {
    string input;
    while (getline(cin, input)) {
        replace(input);
        cout << input << endl;
    }
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int x,y;
	while(1){
		cin >> x >> y;
		if(x==0&&y==0)break;
		if(x>y)cout<<y<<" "<<x<<endl;
		else cout<<x<<" "<<y<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
#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;
#define P pair<int,int>
vector<int> G[100010];
int c[100010];
int ans[100010];
int cnt;
int sum;
void dfs(int v, int parent) {
	ans[v] = c[cnt++];
	for (int to: G[v]) {
		if (to == parent) continue;
		sum += c[cnt];
		dfs(to, v);
	}
}
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for (int i = 0; i < N; i++) cin >> c[i];
	sort(c, c + N, greater<int>());
	P point = { 0,0 };
	for (int i = 0; i < N; i++) {
		point = max(point, { G[i].size(),i });
	}
	dfs(point.second, -1);
	cout << sum << endl;
	for (int i = 0; i < N; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
}

Measured memory_bytes: 3328
N = int(input())
S = input()

ans_temp = 0
for i in range(1, N):
    if S[i] == 'E':
        ans_temp += 1
ans = ans_temp

for i in range(1, N):
    if S[i] == 'E':
        ans_temp -= 1
    if S[i-1] == 'W':
        ans_temp += 1
    ans = min(ans, ans_temp)

print(ans)

Measured memory_bytes: 9492
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int A, B, C, D, E, F;
	cin >> A >> B;
	C = A + (A - 1);
	D = B + (B - 1);
	E = A + B;
	F = max({ C,D,E });
	cout << F << endl;
	system("pause");
	return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};


int main(){
  
  int n;
  cin >> n;
  vector<int> v(n);
  REP(i,n)cin >> v[i];
  vector<int> u;
  u = v;
  sort(ALL(u),greater<int>());
  REP(i,n){
    if(v[i] == u[0])cout << u[1] << endl;
    else cout << u[0] << endl;
  }


  return 0;
}


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

int n;

int main(void) {
	int maxval, minval;
	cin >> n;

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

	maxval = R[1] - R[0]; // 初期値
	minval = R[0]; // 売る時より以前の買値の最小

	for (int j = 1; j <= n - 1; j++) {
		maxval = max(maxval, R[j] - minval);
		minval = min(minval, R[j]); // 今回の値が今までの最小値より低いかどうか
	}

	cout << maxval << endl;

	return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main() {
	string s, t;
	cin >> s >> t;
	if (s[0] == t[2] && s[1] == t[1] && s[2] == t[0])
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}



Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    if(a < b && b < c){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
    sc.close();
  }
}



Measured memory_bytes: 26160
import bisect
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.141592653589
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def pscl(num,l=[1]):
    for i in range(num):
        l = map(lambda x,y:x+y,[0]+l,l+[0])
    return l

l=[]
for i in range(1,5001):
    if i%2==0:
        l.append((1+i)*(i/2))
    else:
        l.append((1+i)*(i/2)+(i+1)/2)
n=int(raw_input())
#if n in l:
#    for i in range(1,l.index(n)+2):
#        print i
#        exit()
chk=bisect.bisect_right(l,n)
tmp=l[chk]
for i in range(1,chk+2):
    if i!=tmp-n:
        print i

Measured memory_bytes: 11760
using System;
using System.Linq;

namespace arc069_a
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] x = Console.ReadLine().Split().Select(long.Parse).ToArray();
            if (x[0] * 2 > x[1])
            {
                Console.WriteLine(x[1] / 2);
            }
            else
            {
                Console.WriteLine((x[0] + x[1] / 2) / 2);
            }
            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 13268
#include <iostream>
using namespace std;
int n,k,t=0;
bool prime(int o)
{
    if(o<2)return false;
    for(int i=2;i*i<=o;i++)if(o%i==0)return false;
    return true;
}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>k;
        if(prime(k))t++;
    }
    cout<<t<<endl;
    return 0;
}


Measured memory_bytes: 3092
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

const long long int INF = 1e9;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define Rep(i, n) for(int i = 1; i <= (int)(n); i++)
#define llrep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define llRep(i, n) for(ll i = 1; i <= (ll)(n); i++)

using namespace std;

struct Point{
	int x,y;
};

bool vector_finder(std::vector<int> vec, int number) {
    auto itr = std::find(vec.begin(), vec.end(), number);
    size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return true;
    }
  else { // 発見できなかったとき
    return false;
    }
}

int main(){
    ll sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;
    ll x = abs(sx - tx);
    ll y = abs(sy - ty);
    // cout << "x = " << x;
    // cout << "y = " << y;


    rep(i,y) cout << 'U';
    rep(i,x) cout << 'R';

    rep(i,y) cout << 'D';
    rep(i,x) cout << 'L';

    cout << 'L';
    rep(i,y+1) cout << 'U';
    rep(i,x+1) cout << 'R';
    cout << 'D';

    cout << 'R';
    rep(i,y+1) cout << 'D';
    rep(i,x+1) cout << 'L';
    cout << 'U';
    
    cout << "" << endl;
    return 0;
}


Measured memory_bytes: 256
//#pragma region ALL(include define etc)
#include <iostream>   // swap(a, b)
#include <string>
#include <cmath>      // abs(絶対値) sin cos tan(角度 / 180.0 * 3.141592)
#include <vector>     // vec.push_back(a) vec.pop_back()
#include <algorithm>  // max(a, b) min(a, b) reverse() sort()
#include <functional> // sort(a, a + N, greater<型>());
#include <math.h>
#include <iomanip>
#define int long long
#define ll long long
//#define double long double
using namespace std;
//#pragma endregion

signed main()
{
	//int x;

	//int h1, h2, m1, m2, k;
	//int box, box1,box2;

	//int N;
	int n;
	//int m;
	//int k;
	//string s;
	string t;
	//int m1, m2;
	//int a, b, c, k;

	//long double aaa;

	//int k, d;
	//int all = 0;
	//double all;
	//double a, b;
	//double h, m;
	//int a[30000] = { 0 };
	//double c, d, e;

	//double mbox, hbox;
	//double box, box2;

	//int b = 0;

	//int box[10000] = { 0 };

	//bool flag = true;

	//string str;

	//cin >> h1 >> m1 >> h2 >> m2 >> k;
	cin >> t;

	n = t.length();
	
	//cout << b << "\n";
	for (int i = 0; i < n; i++)
	{
		if (t[i] == '?')
		{
			t[i] = 'D';
		}
	}

	/*if (flag == true)
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}*/

	cout << t << "\n";

	//cout << fixed << setprecision(111) << all;
}

Measured memory_bytes: 3752
#include<iostream>
#include<cstdio>
#include<iomanip>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int main(){
    int N;
    cin >> N;
    int sub = N/15;
    int ans = N*800-sub*200;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import Counter
n = int(input())
words = [input() for i in range(n)]

counter = Counter(words).most_common()
ans =[]
for i in range(int(len(counter))):
    if counter[0][1] > counter[i][1]:
        break
    ans.append(counter[i][0])
ans.sort()

for i in ans:
    print(i)

Measured memory_bytes: 45040
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pq priority_queue
#define vi vector<int>
#define vl vector<long long>
#define vii vector<vector<int>>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;



int main()
{
    
    char C;
    cin >> C;
    cout << char(C + 1) << endl;


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cassert>
#include <iomanip>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const int iINF = 1001001001;
const long long llINF = 1LL << 60;
int main()
{
    /*string s; cin >> s;
    int ans = 0;
    if (s[0] == 'R' && s[1] == 'R' && s[2] == 'R') ans = 3;
    else if (s[0] == 'R' && s[1] == 'R') ans = 2;
    else if (s[2] == 'R' && s[1] == 'R') ans = 2;
    else {
        if (s[0] == 'R' || s[1] == 'R' || s[2] == 'R') ans = 1;
    }
    cout << ans << endl;
    */

    int n; cin >> n;
    vector<ll> l(n);
    rep(i, n) cin >> l[i];
    ll ans = 0;
    rep(i, n) {
        for(int j = i + 1; j < n; ++j) {
            for(int k = j + 1; k < n; ++k) {
                if (l[i] == l[j] || l[j] == l[k] || l[k] == l[i]) continue;
                ll mx = max(l[i], l[j]);
                mx = max(mx, l[k]);
                ll others = 0;
                if (mx != l[i]) others += l[i];
                if (mx != l[j]) others += l[j];
                if (mx != l[k]) others += l[k];
                if (mx < others) ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
from math import floor

def func(a,b):
    return max(len(str(a)),len(str(b)))

n = int(input())

ans = 10

sup = floor(pow(n,1/2))
for p in range(1,sup+1):
    if n % p == 0:
        ans = min(ans,func(p,n//p))

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
using pll=pair<ll,ll>;

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define MOD 1000000007

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


bool bisearch(vector<int>& s, int n) {
	int left = -1, right = s.size();
	while(right - left > 1) {
		int mid = (right + left) / 2;
		if(s[mid] <= n) left = mid;
		else right = mid;
	}
	if(s[left] == n) return true;
	else return false;
}

int main() {
	int n,q;
	cin >> n;
	vector<int> s(n);
	rep(i,n) cin >> s[i];
	cin >> q;
	vector<int> t(q);
	rep(i,q) cin >> t[i];
	int count = 0;
	rep(i,q) {
		if(bisearch(s, t[i])) count++;
	}
	cout << count << endl;

  return 0;
}


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

int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> vec(H);
  for (int i = 0; i < H; i++){
    cin >> vec.at(i);
  }
  for (int i = 0; i < W + 2; i++){
    cout << "#";
  }
  cout << endl;
  for (int i = 0; i < H; i++){
    cout << "#" << vec.at(i) << "#" << endl;
  }
  for (int i = 0; i < W + 2; i++){
    cout << "#";
  }
  cout << endl;
}

Measured memory_bytes: 256
package main

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

func main() {
	fsc := NewFastScanner()
	N := fsc.NextInt()
	T := make([]int64, 0)
	for i := 0; i < N; i++ {
		T = append(T, fsc.NextInt64())
	}
	var res int64
	res = 1
	for _, val := range T {
		res = res / Int64Gcd(res, int64(val)) * int64(val)
	}
	fmt.Println(res)
}

//template
type FastScanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewFastScanner() *FastScanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1024)
	return &FastScanner{r: rdr}
}
func (s *FastScanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *FastScanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *FastScanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *FastScanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *FastScanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *FastScanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}

//Max,Min
func IntMax(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func Int64Max(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}
func Float64Max(a, b float64) float64 {
	if a < b {
		return b
	}
	return a
}

func IntMin(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func Int64Min(a, b int64) int64 {
	if a > b {
		return b
	}
	return a
}
func Float64Min(a, b float64) float64 {
	if a > b {
		return b
	}
	return a
}

//Gcd
func IntGcd(a, b int) int {
	if a < b {
		b, a = a, b
	}
	if b == 0 {
		return a
	}
	return IntGcd(b, a%b)
}
func Int64Gcd(a, b int64) int64 {
	if a < b {
		b, a = a, b
	}
	if b == 0 {
		return a
	}
	return Int64Gcd(b, a%b)
}

func IntAbs(a int) int {
	if a < 0 {
		a *= -1
	}
	return a
}

func Int64Abs(a int64) int64 {
	if a < 0 {
		a *= -1
	}
	return a
}


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

bool check(string s) {
  bool ok = true;
  for (int i = 0;i<s.size();i++) {
    if (s.at(i) != s.at(s.size()-1-i)) ok = false;
  }
  return (ok);
}


int main() {
  string s;
  cin >> s;
  string a1 = s.substr(0,(s.size()-1)/2);
  string a2 = s.substr((s.size()+3)/2 - 1);
  if (check(s) && check(a1) && check(a2)) cout << "Yes" << endl;
  else cout << "No" << endl;
  //cout << a1 << endl;
  //cout << a2 << endl;
}



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

int main(){
    string S; int Q;
    cin >> S >> Q;

    vector<int> T(200010), F(200010); vector<char> C(200010);
    
    bool rev = false;
    rep(q, Q){
        cin >> T[q];
        if(T[q] == 1) rev = !rev;
        if(T[q] == 2) cin >> F[q] >> C[q];
    }

    bool head = true; string left, right;
    rep(q, Q){
        if(!rev){
            if(T[q] == 1) head = !head;
            if(T[q] == 2){
                if((F[q] == 1 && head) || (F[q] == 2 && !head)) left = C[q] + left;
                if((F[q] == 2 && head) || (F[q] == 1 && !head)) right = right + C[q];  
            }
        } else {
            if(T[q] == 1) head = !head;
            if(T[q] == 2){
                if((F[q] == 1 && head) || (F[q] == 2 && !head)) left = left + C[q];
                if((F[q] == 2 && head) || (F[q] == 1 && !head)) right = C[q] + right;  
            }
        }
    }

    if(rev){
        reverse(S.begin(), S.end());
        cout << right+ S + left << endl; return 0;
    } else {
        cout << left + S + right << endl; return 0;
    }
}


Measured memory_bytes: 3268
#include <bits/stdc++.h>
 
#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < (n); i++)
#define forr(i,a,b) for (int i = (a); i <= (b); i++)
#define all(v) v.begin(), v.end()
#define pb push_back
 
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ii> vii;

const int MX = 200005;
int n, m, K, a[12][1002], res, acu[102];

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n >> m >> K;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			a[i][j] = c - '0';
		}

	res = (n - 1) * (m - 1);
	for (int k = (1 << n - 1); k < (1 << n); k++) {
		int c = __builtin_popcount(k) - 1;
		memset(acu, 0, sizeof(acu));

		for (int j = 0; j < m; j++) {
			int act = 0;

			for (int i = 0; i < n; i++) {
				act += a[i][j];

				if (k & (1 << i)) {
					if (act > K) {
						c = -1;
						break;
					}

					if (acu[i] + act > K) {
						memset(acu, 0, sizeof(acu));
						c++;

						act = 0;
						for (int l = 0; l < n; l++) {
							act += a[l][j];
							acu[l] = act;

							if (k & (1 << l))
								act = 0;
						}

						break;
					}

					acu[i] += act;
					act = 0;
				}
			}

			if (c == -1) break;
		}

		if (c != -1) res = min(res, c);
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 384
#include<cstring>
#include<bits/stdc++.h>
#define mod 1000000007
#define INF 1000000007
using namespace std;
typedef long long ll;
int main()
{
    //freopen("input.txt","r",stdin);
    int n;
    cin>>n;
    if(n==1)
        puts("Hello World");
    else
    {
        int a,b;
        cin>>a>>b;
        cout<<a+b<<endl;
    }
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	pair< pair<string, int>, int> P[n];
	for (int i = 0; i < n; i++) {
		cin >> P[i].first.first >> P[i].first.second;
		P[i].first.second *= -1;
		P[i].second = i + 1;
	}
	sort(P, P + n);
	for (auto e : P) cout << e.second << endl;
	return 0;
}

Measured memory_bytes: 256
S=input()
T=input()

ok=True
a,b={},{}
for i in range(len(S)):
  s=S[i]
  t=T[i]
  if s in a:
    if a[s]!=t:
      ok=False
  if t in b:
    if b[t]!=s:
      ok=False
  a[s]=t
  b[t]=s

print("Yes" if ok else "No")


Measured memory_bytes: 73420
#include<bits/stdc++.h>
using namespace std;
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define pb push_back
#define F first
#define S second

#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define int long long
#define ll long long
const int M=1e9+7;

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

int expo(int x, int y) {int res=1;x=x%M;while(y>0){if(y&1)res=(1ll*res*x)%M;
	y=y>>1;x=(1ll*x*x)%M;} return res;}
	

signed main(){
	gearup;
	int t = 1;
	//cin >> t;
	while(t--){
		int n, x; 
		cin >> n;
		int a[n + 1] = {};
		for(int i = 0 ; i < n - 1; i++){
			cin >> x;
			a[x]++;	
		}
		for(int i = 1 ; i <= n ;i++)
			cout << a[i] << "\n";
	}
	return 0;
}

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

int print(bool ok) {
        if (ok) cout << "Possible" << endl;
        else cout << "Impossible" << endl;
        return 0;
}

int main() {
        int n, a;
        cin >> n;
        int mi = 110;
        int cnt[200] = { 0 };
        for (int i = 0; i < n; i ++) { 
                cin >> a;
                cnt[a] ++;
                mi = min(mi, a);
        }
        if (cnt[mi] > 2) return print(0);
        for (int i = mi + 1; i < 2 * mi + (cnt[mi] == 1 ? 1 : 0); i ++) if (cnt[i] < 2) return print(0);
        for (int i = 2 * mi + (cnt[mi] == 1 ? 1 : 0); i < 200; i ++) if (cnt[i] > 0) return print(0);
        return print(1);
}


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

A_survive = list(reversed(A))
B_avail = list(reversed(B))
ans = 0

for i in range(N):
  if A_survive[i] < B_avail[i]:#
    B_avail[i] -= A_survive[i]
    ans += A_survive[i]
    if B_avail[i] < A_survive[i+1]:
      ans += B_avail[i]
      A_survive[i+1] -= B_avail[i]
      B_avail[i] = 0
    else:
      ans += A_survive[i+1]
      B_avail[i] -= A_survive[i+1]
      A_survive[i+1] = 0
  else:
    ans += B_avail[i]
    B_avail[i] = 0

#print(*A_survive)
#print(*B_avail)
print(ans)

Measured memory_bytes: 19004
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
typedef long long ll;
static const ll MOD = 1e9 + 7;
static const ll INF = (ll)1 << 62;

static const int MAX = 100001;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;
vector<pair<int, int>> adj[MAX];

ll p[MAX];
ll d[MAX];
bool visit[MAX];
priority_queue<pair<int, int>>PQ;
ll n;
void dijkstra(int s) {
	repe(i, 1, n) {
		d[i] = INF;
		p[i] = INF;
	}

	d[s] = 0;
	p[s] = -1;
	PQ.push(make_pair(s, s)); // ?reverse?
	//color[s] = GRAY;

	while (!PQ.empty()) {
		pair<ll, ll> f = PQ.top(); PQ.pop();
		ll u = f.second;

		visit[u] = true;

		if (d[u] < f.first * (-1)) continue;

		rep(j, 0, adj[u].size()) {
			ll v = adj[u][j].first;
			if (visit[v]) continue;
			if (d[v] > d[u] + adj[u][j].second) {
				d[v] = d[u] + adj[u][j].second;
				PQ.push(make_pair(d[v] * (-1), v));
				p[v] = u;
			}
		}
	}
	//rep(i, 0, n) cout << i << " " << (d[i] == INF ? -1 : d[i]) << endl;
	//rep(i, 0, n) cout << i << " " << (p[i] == INF ? -1 : p[i]) << endl;
}

vector<ll> get_path(int t) {
	vector<ll> path;
	for (; t != -1; t = p[t])path.push_back(t);
	reverse(path.begin(), path.end());
	return path;
}

int main()
{
	cin >> n;
	rep(i, 0, n - 1) {
		ll a, b, c; cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
	}
	ll q, k; cin >> q >> k;

	dijkstra(k);

	rep(i, 0, q) {
		ll x, y; cin >> x >> y;
		cout << d[x] + d[y] << endl;
	}
	return 0;
}

Measured memory_bytes: 10100
MOD = 998244353
def main():
    import sys
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    fu = FactorialUtils(N)
    ans = Mint()
    for i in range(K + 1):
        tmp = Mint(1)
        tmp *= fu.choose(N - 1, i)
        tmp *= M
        tmp *= pow(M - 1, N - 1 - i, MOD)
        ans += tmp
    print(ans)

class FactorialUtils:
    def __init__(self, n, mod=MOD):
        self.__mod = mod
        self.fac = [1] * (n + 1)
        self.ifac = [1] * (n + 1)
        for i in range(2, n + 1): self.fac[i] = self.fac[i - 1] * i % mod
        self.ifac[n] = pow(self.fac[n], mod - 2, mod)
        for i in range(n, 1, -1): self.ifac[i - 1] = self.ifac[i] * i % mod

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.ifac[n - r] % self.__mod) * self.ifac[r] % self.__mod

    def multichoose(self, u, k):
        return (self.fac[u + k - 1] * self.ifac[u - 1] % self.__mod) * self.ifac[k] % self.__mod

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj


if __name__ == '__main__':
    main()


Measured memory_bytes: 71080