akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;

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

#define all(c) (c).begin(), (c).end()
#define pb push_back
#define mp make_pair
#define EXIST(v,i) (find(all(v), i) != (v).end())
#define ERASE(v,i) (v).erase(remove(all(v), i), (v).end())
#define INDEX(v,i) (find(all(v), i) - (v).begin())
#define rep(i,n) for(int i = 0; i < (int)n; ++i)
#define debug(x) cerr << #x << " = " << (x) << endl;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

const int INF = 100000000;
const double PI = 3.14159265358979323846;
const double EPS = 1e-10;

int main() {
	int CaseSet = 1;
	for(int W; scanf("%d", &W), W;) {
		int N; scanf("%d", &N);
		vector<int> value(N);
		vector<int> weight(N);
		rep(i,N) scanf("%d,%d", &value[i], &weight[i]);

		int dp[N][W+1];
		memset(dp, 0, sizeof dp);
		for(int j = weight[0]; j <= W; j++) dp[0][j] = value[0];
		for(int i = 1; i < N; i++) {
			memcpy(dp[i], dp[i -1], sizeof dp[i]);
			for(int j = weight[i]; j <= W; j++) {
				int t = dp[i - 1][j - weight[i]] + value[i];
				dp[i][j] = max(dp[i][j], t);
			}
		}

#if 0
		rep(i,N) {
			rep(j,W) cerr << " " << dp[i][j];
			cerr << endl;
		}
#endif

#if 0
		int vans = *max_element(dp[N-1], dp[N-1] + W);
		int minweight = find(dp[N-1], dp[N-1] + W, vans) - dp[N-1];
#endif

#if 1
		int vans = dp[N-1][W];
		int minweight = W;
		for(int j = W - 1; j >= 0; --j) {
			if(dp[N-1][j] >= vans) {
				minweight = j;
				vans = dp[N-1][j];
			}
		}
#endif

		cout << "Case " << CaseSet++ << ":" <<endl;
		cout << vans << endl;
		cout << minweight << endl;
	}
	return 0;
}

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

using namespace std;

const int MAXN = 200200;

int N;
vector<int> adj[MAXN];
int dist[MAXN];
vector<int> byDist[2];
bool wv[MAXN];
bool wa[MAXN];
int ans[MAXN];

void dfs(int v, int p) {
   byDist[dist[v] & 1].emplace_back(v);
   for (int u : adj[v]) {
      if (u != p) {
         dist[u] = dist[v] + 1;
         dfs(u, v);
      }
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> N;
   for (int i = 0; i < N - 1; ++i) {
      int v, u;
      cin >> v >> u;
      adj[v].emplace_back(u);
      adj[u].emplace_back(v);
   }
   dfs(1, -1);
   if (byDist[0].size() > byDist[1].size()) {
      swap(byDist[0], byDist[1]);
   }
   if (byDist[0].size() <= (N / 3)) {
      int start = 3;
      for (int v : byDist[0]) {
         ans[v] = start;
         wv[v] = true;
         wa[start] = true;
         start += 3;
      }
   } else {
      int start = 2;
      for (int v : byDist[0]) {
         if (start <= N) {
            ans[v] = start;
            wv[v] = true;
            wa[start] = true;
            start += 3;
         }
      }
      start = 1;
      for (int v : byDist[1]) {
         if (start <= N) {
            ans[v] = start;
            wv[v] = true;
            wa[start] = true;
            start += 3;
         }
      }
   }
   int ptr = 1;
   for (int i = 1; i <= N; ++i) {
      if (!wv[i]) {
         while (wa[ptr]) ptr++;
         ans[i] = ptr++;
      }
      cout << ans[i] << " ";
   }
}


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

int main(void) {
  int N, Y;
  cin >> N >> Y;
  
  bool flag = false;
  for(int i = 0; i <= N; i++){
    for(int j = 0; j <= N - i; j++){
      if(10000 * i + 5000 * j + 1000 * (N - i - j) == Y){
        cout << i  << " " << j  << " " << N - i - j << endl;
        flag = true;
        break;
      }
    }
    if(flag)break;
  }
  
  if(!flag)cout << -1 << " " << -1 << " " << -1 << endl;

  return 0;
}

Measured memory_bytes: 888
#include<stdio.h>


int main(void){
    int A,B;
    int count = 0;
    int KETA[5]={};
    scanf("%d %d",&A,&B);
    for(int i = A;i<=B;i++){
        int num = i;
        for(int j=0;j<5;j++){
            KETA[j] = num%10;
            num = num/10;
        }
        if(KETA[0]==KETA[4]&&KETA[1]==KETA[3]){
            count ++ ;
        }
    }
    printf("%d",count);
    return 0;
}

Measured memory_bytes: 128
from itertools import accumulate
from bisect import bisect_right


def main():
    children, cookies = map(int, input().split())
    target = sorted(list(map(int, input().split())))
    sum_target = sum(target)
    if sum_target < cookies:
        print(children - 1)
    elif cookies < target[0]:
        print(0)
    else:
        accumulate_target = list(accumulate(target))
        print(bisect_right(accumulate_target, cookies))


if __name__ == '__main__':
    main()



Measured memory_bytes: 3188
a=b=1
gets.to_i.times do
  c,d=gets.split.map(&:to_i)
  a=[a.to_r/c,b.to_r/d].max.ceil*c
  b=[a.to_r/c,b.to_r/d].max.ceil*d
end
p (a+b).to_i

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

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define FastIO ios::sync_with_stdio(0); cin.tie(0);

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vpl;
typedef map<ll, ll> mll;
typedef map<string, ll> msl;
#define md 1000000007

void minn(ll &a, ll b)
{
    a = min(a,b);
}

void maxx(ll &a, ll b)
{
    a = max(a,b);
}

void mod(ll &a)
{
    if(a>=md)
    {
        a -= md;
    }
}

vl dp;
vector<bool> stair;

ll f(ll a)
{
    if(a < 0 or !stair[a])
    {
        return 0;
    }
    if(a == 0)
    {
        return 1;
    }
    if(dp[a] != -1)
    {
        return dp[a];
    }
    dp[a] = f(a-1) + f(a-2);
    mod(dp[a]);
    return dp[a];
}

int main()
{
    FastIO
    ll n, m; cin >> n >> m;
    dp.resize(n+1,-1);
    stair.resize(n+1,true);
    for (int i = 0; i < m; i++)
    {
        ll x; cin >> x;
        stair[x] = false;
    }

    cout << f(n) << '\n';
    
    return 0;
}

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

int main() {
  int n, m;
  cin >> n;
  map<string, int> s, t;
  string tmp;
  for (int i=0; i<n; i++) {
    cin >> tmp;
    s[tmp]++;
  }
  cin >> m;
  for (int i=0; i<m; i++) {
    cin >> tmp;
    t[tmp]++;
  }
  vector<int> ans;
  for (map<string, int>::iterator i = s.begin(); i != s.end(); i++) {
    ans.push_back(i->second - t[i->first]);
  }
  sort(ans.begin(), ans.end(), greater<int>());
  if (ans[0] > 0) cout << ans[0] << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc143/tasks/abc143_d
#include <iostream>
#include <vector>
#include <algorithm>

bool isTriangle(int a, int b, int c)
{
	return (a + b) > c && (b + c) > a && (a + c) > b;
}

int main()
{
	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);

	int nums_count = 0;
	std::cin >> nums_count;
	std::vector<int> numbers(nums_count);
	for (auto& val : numbers)
	{
		std::cin >> val;
	}

	int num_triangles = 0;

	std::sort(numbers.begin(), numbers.end());

	for (size_t i = 0; i < numbers.size(); ++i)
	{
		for (size_t j = i+1; j < numbers.size(); ++j)
		{
			const int sum_2 = numbers[i] + numbers[j];
			for (size_t k = j+1; k < numbers.size(); ++k)
			{
				if (numbers[k] < sum_2)
					++num_triangles;
				else
					break;
			}
		}
	}

	std::cout << num_triangles;
}

Measured memory_bytes: 256
N = int(input())
t,x,y = 0,0,0
for i in range(N):
    T,X,Y = map(int,input().split())
    d = abs(x-X)+abs(y-Y)
    if (T-t)-d >= 0 and ((T-t)-d)%2 == 0:
        t,x,y = T,X,Y
        continue
    else:
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 3064
s = input()
num = len(s)

kb = []

for i in range(num):
    kb.append(s[i])

mae = 0
usi = num-1
ans = 0

while mae < usi:
    #print(i)
    if s[mae] != s[usi]:
        if s[mae] == 'x':
            #kb.append('x')
            ans += 1
            mae += 1
        elif s[usi] == 'x':
            #kb.insert(mae,'x')
            ans += 1
            usi -= 1
        else:
            print(-1)
            exit()
    else:
        mae += 1
        usi -= 1

print(ans)

Measured memory_bytes: 4212
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d;
long long max(long a,long b)
{
	return a>b?a:b;
}
int main()
{
	cin>>a>>b>>c>>d;
	cout<<max(max(a*c,a*d),max(b*c,b*d));
}

Measured memory_bytes: 3576
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <time.h>
#pragma warning(disable:4996) 

typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

char str[200005];

void solve()
{
    scanf("%s", str);
    int n = strlen(str);
    int ans = 0;
    int i;
    for (i = 0; i < n; i++) {
        ans = (ans + str[i] - '0') % 9;
    }
    if (ans == 0) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }

    return;
}

int main()
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for (t = 0; t < T; t++) {
        //printf("Case #%d: ", t + 1);
        solve();
    }
#endif
    return 0;
}


Measured memory_bytes: 1796
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>

#define ll unsigned long long
#define INF 0x3f3f3f3f
#define clr(x) memset(x,0,sizeof(x))
#define clr2(x) memset(x,INF,sizeof(x))
#define clr3(x) memset(x,-INF,sizeof(x))
#define clr4(x) memset(x,-1,sizeof(x))
#define pb(x) push_back(x)
//#define debug

using namespace std;
const ll mod=1e9+7;

ll a,b,x,res;
void solve()
{
    scanf("%lld%lld%lld",&a,&b,&x);
    if (a==0)
        res=b/x + 1;
    else
    res=b/x- (a-1)/x;
    printf("%lld\n",res);
}
int main()
{
    #ifdef debug
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif


        solve();


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Mod = (ll) (1e9) + 7;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
ll bpowMod(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1)
      res = (res * a) % Mod;
    a = (a * a) % Mod;
    b >>= 1;
  }
  return res % Mod;
}
ll combinationMod(ll n, ll r) {
  if (r * 2 > n)
    r = n - r;
  ll nd = 1;
  ll rd = 1;
  for (ll i = 1; i <= r; ++i) {
    nd = nd * (n - i + 1) % Mod;
    rd = rd * i % Mod;
  }
  return nd * bpowMod(rd, Mod - 2) % Mod;
}
int main() {
  ll n, a, b, c = 0;
  cin >> n >> a >> b;
  c += combinationMod(n, a);
  c += combinationMod(n, b);
  c %= Mod;
  ll ans = bpowMod(2, n) % Mod;
  cout << (ans - c - 1 + Mod) % Mod;
}


Measured memory_bytes: 256
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)

def main():
    n, m = map(int, input().split())

    dag = [[] for _ in range(n+1)]
    for _ in range(m):
        src, dst = map(int, input().split())
        dag[src].append(dst)


    dists = [0] * (n+1)

    def longest(v):
        if dists[v]:
            return dists[v]
        for to in dag[v]:
            dists[v] = max(dists[v], longest(to) + 1)
        return dists[v]

    ans = 0
    for i in range(1, n+1):
        ans = max(ans, longest(i))

    print(ans)


if __name__ == '__main__':
    main()



Measured memory_bytes: 67600
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define MOD 1000000007
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(v) (v).begin() , (v).end()
#define sumof(v) accumulate(all(v), 0LL, plus<ll>())
#define maxof(v) max_element(all(v))
#define minof(v) min_element(all(v))
#define inf INT_MAX

int main(){
    FASTIO
    ll n, x, t; cin>>n>>x>>t;
    cout<<(int)ceil((1.0*n)/x)*t<<endl;
}



Measured memory_bytes: 3648
#include <iostream>
#include <math.h>
#include <limits>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <map>
#include <utility>
using namespace std;
#define rep(i, n) for (int i =0; i < (int)(n); i++)
typedef pair<int, string> P;




int main() {
    string  s;
    cin >> s;
    if (s == "ABC")cout << "ARC" << endl;
    else cout << "ABC" << endl;

    
}



Measured memory_bytes: 3624
from collections import defaultdict
from copy import deepcopy
from math import log

N,M=map(int,input().split())
def prime_factor(n):
    i = 2
    table = defaultdict(int)
    while i * i <= n:
        while n % i == 0:
            n //= i
            table[i]+=1
        i += 1
    if n > 1:
        table[n]+=1
    return table
f=prime_factor(M)
L=[1]
for i in f.keys():
    l=[]
    for j in range(f[i]+1):
        l.extend([k*(i**j) for k in L])
    L=l
L.sort()
for i in L[::-1]:
    if i>=N:
        ans=i
        continue
    break
print(M//ans)


Measured memory_bytes: 38512
from typing import List


class Dice:

    sur = [i for i in range(6)]

    def __init__(self, s: List[int]):
        self.s = s  # surfaceリスト

        # indexが面の番号。リストの値は、それに接する面の番号。
        self.sur[0] = [1, 2, 4, 3]
        self.sur[1] = [0, 3, 5, 2]
        self.sur[2] = [1, 5, 4, 0]
        self.sur[3] = [1, 0, 4, 5]
        self.sur[4] = [0, 2, 5, 3]
        self.sur[5] = [1, 3, 4, 2]

    def get_right_face_num(self, upper_num: int, front_num: int) -> int:
        for i, value in enumerate(self.sur[upper_num]):
            if value == front_num:
                return self.sur[upper_num][(i + 1) % 4]
        else:
            raise ValueError('get_right_faceの来てはいけない箇所')

    def get_value(self, face_num) -> int:
        return self.s[face_num]

    def get_face_num(self, value) -> int:
        for i in range(len(self.s)):
            if value == self.s[i]:
                return i
        else:
            raise ValueError('get_sur_indexの来てはいけない箇所')


# 提出用
data = [int(i) for i in input().split()]
N = int(input())
dice = Dice(data)
for _i in range(N):
    upper_value, front_value = map(int, input().split())
    upper_num = dice.get_face_num(upper_value)
    front_num = dice.get_face_num(front_value)
    ans_num = dice.get_right_face_num(upper_num, front_num)
    print(dice.get_value(ans_num))

# # 動作確認用
# with open('input_itp1_11_a_1.txt', mode='r', encoding='utf8') as fin:
#     data = [int(i) for i in next(fin).split()]
#     N = int(next(fin))
#     dice = Dice(data)
#     for _i in range(N):
#         upper_value, front_value = map(int, next(fin).split())
#         upper_num = dice.get_face_num(upper_value)
#         front_num = dice.get_face_num(front_value)
#         ans_num = dice.get_right_face_num(upper_num, front_num)
#         print(dice.get_value(ans_num))



Measured memory_bytes: 7168
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void go();
int main() {
#ifdef tokitsukaze
    freopen("TEST.txt", "r", stdin);
#endif
    go();
    return 0;
}

/*********************************  head  *********************************/


int n,a[100100],m[100100];
LL ans;
void go() {
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        m[i]=a[i]+m[i-1];
        ans+=a[i]*m[i-1];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner s = new Scanner(System.in);

    int a = s.nextInt();
    int b = s.nextInt();
    int c = s.nextInt();

    int d = a+b;
    int e = a+c;
    int f = b+c;

    int[] g = {d,e,f};
    int h = g[0];

    for(int i = 0; i < g.length; i++){
      h = Math.min(h,g[i]);

    }
    System.out.println(h);
  }
}


Measured memory_bytes: 22740
//
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
//
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 mut $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")
    };
}

// solution 
use std::cmp;
#[allow(unused_mut)]
#[allow(non_snake_case)]
fn main() {
    input!{
        N: usize,
        K: usize,
        S: chars,
    }

    let mut interval_length = Vec::new(); 
    let mut ind = 0;
    while ind < S.len() {
        let mut count = 1;
        if ind+1 >= S.len() {
            interval_length.push(count);
            break
        }
        while S[ind] == S[ind+1] {
            count += 1;
            ind += 1;
            if ind >= S.len()-1 {
                break
            }
        }
        interval_length.push(count);
        ind += 1;
    }

    if S.last().unwrap() == &'0' {
        interval_length.push(0);
    }
    if S[0] == '0' {
        interval_length.insert(0, 0);
    }

    let max_op = interval_length.len() / 2;
    if K >= max_op {
        println!("{}", interval_length.iter().sum::<usize>());
        return
    }

    let mut sum = interval_length.iter().take(2*K+1).sum::<usize>();
    let mut prev = sum;
    let mut max = sum;
    for kstart in 0..(max_op-K) {
        sum = prev + interval_length[2*(K+kstart)+1] + interval_length[2*(K+kstart)+2] - interval_length[2*kstart] - interval_length[2*kstart+1];
        max = cmp::max(max, sum);
        prev = sum;
    }
    println!("{}", max);
}


Measured memory_bytes: 4352
n = gets.to_i
arr = gets.split.map(&:to_i)
result = 'APPROVED'
(1..n).each do |n| 
  a = arr[n-1]
  if a % 2 == 0
    result = 'DENIED' unless (a % 3 == 0) or (a % 5 == 0)
  end
end

puts result

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i <= (int)(n); i++)
int main() {
  int A, B;
  cin >> A >> B;
  int Xa, Xb, Xc;
  int co = 0;
  rep2(i, A, B) {
    Xa = i % 10;
    Xb = (i - Xa) % 100 / 10;
    Xc = (i - Xa - Xb*10) % 1000 / 100;
    if(Xa * 10001 + Xb * 1010 + Xc * 100 == i) {
      co++;
    }
  }
  cout << co << endl;
}

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

int min(int a, int b) { return (a < b) ? a : b; }
int main(void) {
    string n;
    cin >> n;
    int ans = 0, carry = 0;
    int l = n.length();
    // 0: total banknotes if I pay this digit
    // 1: total banknotes if I let the clerk return on this digit
    int dp[l][2];
    int dg = n[l - 1] - '0';
    dp[l - 1][0] = dg;
    dp[l - 1][1] = 10 - dg;
    for (int i = l - 2; i >= 0; i--) {
        dg = n[i] - '0';
        dp[i][0] = min(dg + dp[i + 1][0], dg + dp[i + 1][1] + 1);
        dp[i][1] = min(10 - dg + dp[i + 1][0], 10 - dg - 1 + dp[i + 1][1]);
    }
    ans = min(dp[0][0], dp[0][1] + 1);
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 9220
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.WriteLine(sb.ToString());
    }
    void Calc(){
        string[] str = Console.ReadLine().Split(' ');
        int A = int.Parse(str[0]);
        int B = int.Parse(str[1]);
        if(A <= B){
            sb.Append("Impossible");
        }
        else{
            int N = A + B;
            int[] stack = new int[N];
            int count = B;
            int sp = 0;
            int p = 0;
            while(sp <= count){
                if(sp == 0){
                    stack[0] = p;
                    sp++;
                    p++;
                }
                else{
                    Console.WriteLine("? "+stack[sp-1]+" "+p);
                    string s = Console.ReadLine();
                    if(s[0] == 'N'){
                        sp--;
                        count--;
                        p++;
                    }
                    else{
                        stack[sp] = p;
                        sp++;
                        p++;
                    }
                }
            }
            int t = sp == 0 ? p : stack[sp-1];
            sb.Append("! ");
            for(int i=0;i<N;i++){
                if(i == t){
                    sb.Append("1");
                }
                else{
                    Console.WriteLine("? "+t+" "+i);
                    string s = Console.ReadLine();
                    sb.Append(s[0] == 'N' ? "0" : "1");
                }
            }
        }
    }
}

Measured memory_bytes: 15612
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

const int inf = 1 << 30;
int H, W;
int dp[310][310];
char mat[310][310];
int ans;

int solve(int l){
    int r = l + 1;
    for(int i = 0; i <= H + 1; i++){
        for(int j = 0; j <= H + 1; j++){
            dp[i][j] = inf;
        }
    }
    for(int i = 0; i <= H; i++){//差
        for(int j = 0; j + i <= H; j++){//片割れの高さ
            if(j == 0) dp[j][j + i] = dp[j + i][j] = 0;
            //lが低い
            chmin(dp[j][j + i], dp[j - 1][j + i - 1] + (mat[j - 1][l] == mat[j + i - 1][r] ? 1 : 0));
            //rが低い
            chmin(dp[j + i][j], dp[j + i - 1][j - 1] + (mat[j + i - 1][l] == mat[j - 1][r] ? 1 : 0));
        }
    }

    for(int i = H; i >= 0; i--){
        for(int j = H; j >= 0; j--){
            if(i == H && j == H) continue;
            dp[i][j] += min(dp[i + 1][j], dp[i][j + 1]);
        }
    }
    return dp[0][0];
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> H >> W;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> mat[i][j];
        }
    }

    for(int l = 0; l + 1 < W; l++){
        ans += solve(l);
    }
    cout << ans << endl;
    return 0;
}

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

#define MAX_N (100000L)
#define MAX_FACT (MAX_N)
#define NUM_MOD (1000000007L)

long fs[MAX_FACT + 1], finvs[MAX_FACT + 1], invs[MAX_FACT + 1];

long mod(long n, long k) { return n % k >= 0 ? n % k : n % k + k; }

void init() {
  fs[0] = fs[1] = 1;
  finvs[0] = finvs[1] = 1;
  invs[1] = 1;
  for (long i = 2; i <= MAX_FACT; i++) {
    fs[i] = fs[i - 1] * i % NUM_MOD;
    invs[i] = NUM_MOD - invs[NUM_MOD % i] * (NUM_MOD / i) % NUM_MOD;
    finvs[i] = finvs[i - 1] * invs[i] % NUM_MOD;
  }
}

int main(int argc, char *argv[]) {
  // read inputs
  long N, as[MAX_N];
  scanf("%ld", &N);
  for (int i = 0; i < N; i++) scanf("%ld", &as[i]);

  // initialize calculation of factorial and mod
  init();

  // calculate the number of times each element gets counted
  long cnts[MAX_N];
  // the first
  cnts[0] = 0;
  for (long i = 0; i < N; i++) {
    cnts[0] = mod(cnts[0] + fs[N] * invs[abs(0 - i) + 1], NUM_MOD);
  }
  // the rest
  for (long i = 1; i < N; i++) {
    cnts[i] = mod(cnts[i - 1] + fs[N] * invs[abs(i - 0) + 1] -
                      fs[N] * invs[abs(i - 1 - (N - 1)) + 1],
                  NUM_MOD);
  }
  for (long i = 0; i < N; i++) {
  }

  // calculate the answer
  long ans = 0;
  for (long i = 0; i < N; i++) {
    // printf("i = %ld, cnts[i] = %ld, as[i] = %ld, cnts[i] = as[i] = %ld\n", i,
    //        cnts[i], as[i], as[i] * cnts[i]);
    ans = mod(ans + as[i] * cnts[i], NUM_MOD);
  }
  printf("%ld\n", ans);

  return 0;
}


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

int main() {
    int n;
    cin >> n;
    int k = 0;
    for(int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        k += t;
    }
    if (k%2 == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main
{
    public static void main(String args[])
    {
	Scanner scan=new Scanner(System.in);
	while(true)
	    {
		int n=scan.nextInt();
		if(n==0)break;
	
		for(int i=0;i<n;i++)
		    {
			int pm,pe,pj;
			pm=scan.nextInt();
			pe=scan.nextInt();
			pj=scan.nextInt();
			if(pm==100 || pe==100 || pj==100)System.out.println("A");
			else if((pm+pe)/2>=90)System.out.println("A");
			else if((pm+pe+pj)/3>=80)System.out.println("A");
			else if((pm+pe+pj)/3>=70)System.out.println("B");
else if((pm+pe+pj)/3>=50 && pm>=80 || pe>=80)System.out.println("B");
else System.out.println("C");
		    }
	    }
	
    }
}

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

using namespace std;
using p=pair<int,int>;
typedef long long ll;

int main() {
  string s,t;
  cin >> s >> t;
  int m = s.size();
  int n = t.size();
  int k = 0;
  rep(i,m-n+1){
    int h=0;
    rep(j,n){
      if(s[i+j]==t[j]){
        h++;
      }
    }
    k = max(k,h);
  }
  cout << n-k << endl;
        
  return 0;

}

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

int main(void)
{
    long long n;
    cin >> n;
    long long a;
    long long max=pow(10,18);
    long long ans=1;
    bool zerocheck=false,maxcheck=false;

    for(int i=0;i<n;i++)
    {
        cin >> a;
        if(a==0)
        {
            zerocheck=true;
        }
        else if(ans > max /a)
        {
            maxcheck=true;
        }
        else
        {
            ans*=a;
        }        
    }
    if(zerocheck)
    {
        cout << 0 << endl;
    }
    else if(maxcheck)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3580
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

int main()
{
    int64_t N, K;
    std::cin >> N >> K;

    struct P {
        int64_t x;
        int64_t y;
    };

    std::vector<P> p;
    std::vector<int64_t> X;
    std::vector<int64_t> Y;
    for (decltype(N) i = 0; i < N; ++i) {
        int64_t x, y;
        std::cin >> x >> y;
        p.push_back({x, y});
        X.push_back(x);
        Y.push_back(y);
    }

    std::sort(std::begin(X), std::end(X));
    std::sort(std::begin(Y), std::end(Y));

    int64_t S = INT64_MAX;

    for (int64_t xs = 0; xs <= N-K; ++xs) {
        for (int64_t xe = xs+K-1; xe < N; ++xe) {
            for (int64_t ys = 0; ys <= N-K; ++ys) {
                for (int64_t ye = ys+K-1; ye < N; ++ye) {
                    auto n = std::count_if(std::begin(p), std::end(p), [&X, &Y, xs, xe, ys, ye](auto e) {
                            return X[xs] <= e.x && e.x <= X[xe] && Y[ys] <= e.y && e.y <= Y[ye];
                        });
                    if (n >= K) {
                        S = std::min(S, (X[xe] - X[xs])*(Y[ye] - Y[ys]));
                    }
                }
            }
        }
    }

    std::cout << S << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define All(vec) vec.begin(), vec.end()
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())
#define PI acos(-1)
typedef long long ll;

int main() {
    int a;
    cin >> a;
    cout << a + a * a + a * a * a << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
const ll mod = 1e9 + 7;

int main()
{
    int n, m;
    cin >> n >> m;
    int a[n] = {0};
    rep(i, m)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (x == 0)
            a[y]++;
        if (y == n - 1)
            a[x]++;
    }
    rep(i, n)
    {
        if (a[i] == 2)
        {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int x[303030];
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++)
	{
		int z;
		scanf("%d", &z);
		z--;
		x[z] = i;
	}
	int now = 1, maxi = 1;
	for (int i = 1; i < num; i++)
	{
		if (x[i - 1] < x[i])now++;
		else now = 1;
		maxi = max(maxi, now);
	}
	printf("%d\n", num - maxi);
}


Measured memory_bytes: 1024
#include<stdio.h>
int main(){
int n,m,s,i,j,w=1e5;
while(scanf("%d%d%d",&n,&m,&s),n){
int d[51][3001]={};d[0][0]=1;
for(i=1;i<=n*n;i++)for(j=i;j<=s;j++){
int &x=d[i][j];x+=d[i-1][j-i]+d[i][j-i];
if(j-1-m>=0)x+=w-d[i-1][j-1-m];x%=w;
}printf("%d\n",d[n*n][s]);
}
return 0;
}


Measured memory_bytes: 1632
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int dp[10001] = { 0 };
	int n, W;
	int v[100], w[100];
	cin >> n >> W;
	for (int i = 0; i < n; i++){
		cin >> v[i] >> w[i];
	}
	for (int i = 0; i < n; i++){
		for (int i2 = 10000; i2 >= 0; i2--){
			if (i2 + w[i] <= W){
				dp[i2 + w[i]] = max(dp[i2 + w[i]], dp[i2] + v[i]);
			}
		}
	}
	cout << dp[W] << endl;
}

Measured memory_bytes: 1208
import Control.Applicative ((<$>))
import Data.Maybe (fromJust)
import Data.List (sort)
import qualified Data.ByteString.Char8 as B

readInts     :: IO [Int]
readInts     = map (fst . fromJust . B.readInt) . B.words <$> B.getLine

main :: IO ()
main = do
  xs <- readInts
  putStrLn $ unwords $ map show $ sort xs


Measured memory_bytes: 3504
N = gets.to_i
A = gets.split.map(&:to_i)
B = gets.split.map(&:to_i)
cnt = 0

N.times do |i|
  # 左側を全力
  left = [A[i], B[i]].min
  cnt += left
  A[i] -= left
  B[i] -= left

  # 右側を全力
  right = [A[i + 1], B[i]].min
  cnt += right
  A[i + 1] -= right
  B[i] -= right
end

puts cnt


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

int main(){
  int r,d,x;
  cin >> r >> d >> x;
  int x2;
  for(int i = 0;i  < 10;i++) {
    x2 = r*x - d;
    x = x2;
    cout << x2 << endl;

  }
}

Measured memory_bytes: 256
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())


ans = 0
commands = [''] * N
for i, t in enumerate(T):
    if t == 'r':
        command = 'p'
        point = P

    elif t == 's':
        command = 'r'
        point = R

    elif t == 'p':
        command = 's'
        point = S

    if (i - K >= 0) and (commands[i -  K] == command):
        command = ''
        point = 0

    ans += point
    commands[i] = command

print(ans)


Measured memory_bytes: 4792
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;


bool isUniqueStr(string s){
	unsigned int char_set[128] = {0};
	rep(i,s.size()) char_set[s[i]]++;
	rep(i,128) if(char_set[i] >= 2) return 0;
	return 1;
}

int main(){
	string s;
	cin >> s;

	bool f = isUniqueStr(s);
	cout << (f ? "yes" : "no") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define UM unordered_map
#define ALL(a) (a).begin(), (a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll, ll> pii;
const ll INF = 1LL << 55;
const ll MOD = 1000000007;
struct Edge
{
    ll s, t, d;
};
typedef vector<vector<Edge>> Graph;
typedef vector<pii> vpii;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

signed main()
{
    int N, K;
    cin >> N >> K;
    vi A, B;
    A.push_back(0);
    B.push_back(0);
    int tmp;

    REP(i, N)
    {
        cin >> tmp;
        if (tmp < 0)
            A.push_back(-1 * tmp);
        else
            B.push_back(tmp);
    }
    sort(ALL(A));
    sort(ALL(B));
    if (A.size() > B.size())
        swap(A, B);

    int ans = INF;
    REP(i, A.size())
    {
        if (i <= K and K-i<B.size())
        {
            chmin(ans, A[i] + 2 * B[K - i]);
            chmin(ans, 2 * A[i] + B[K - i]);
        }
    }
    cout << ans << endl;
    // system("pause");
}


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


int main() {
	int k,n;
  cin>>n>>k;
  
  vector<int> a(n);
  rep(i,n)cin>>a[i];
  
  sort(a.begin(),a.end());
  
   int ans=0; 
  for(int i;i<k;i++){
  	ans+=a[i];
  }
  
  cout<<ans<<endl;
}

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

int main() {
  int n,m;
  cin >> n >> m;
  vector<P> data(m);
  vector<vector<int>> s(n+1);
  rep(i,0,m) {
    int p,y;
    cin >> p >> y;
    data[i] = P(p,y);
    s[p].push_back(y);
  }
  map<P,int> ans;
  rep(i,1,n+1) {
    if ((int)s[i].size() == 0) continue;
    sort(s[i].begin(), s[i].end());
    rep(j,0,(int)s[i].size()) {
      ans[P(i,s[i][j])] = j+1;
    }
  }
  rep(i,0,m) {
    int k = ans[data[i]];
    printf("%06d",data[i].first);
    printf("%06d\n",k);
  }
  return 0;
}


Measured memory_bytes: 15616
n = int(input())

ans = [0 for i in range(n)]
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            n_2 = x ** 2 + y ** 2 + z ** 2 + x*y + x*z + y*z
            if n_2 > int(len(ans)):
                continue
            ans[n_2-1] += 1

for i in range(n):
    print(ans[i])


Measured memory_bytes: 69392
N = int(input())
A = list(map(int, input().split()))
s = abs(A[0]) + abs(A[-1])
for i in range(N-1):
  s += abs(A[i+1] - A[i])
#print(s)
for i in range(N):
  b = A[i]
  if i == 0:
    a = 0
  else:
    a = A[i-1]
  if i == N-1:
    c = 0
  else:
    c = A[i+1]
  if a <= b and b <= c:
    print(s)
  elif a <= c and c <= b:
    print(s-(b-c)*2)
  elif b <= a and a <= c:
    print(s-(a-b)*2)
  elif b <= c and c <= a:
    print(s-(c-b)*2)
  elif c <= a and a <= b:
    print(s-(b-a)*2)
  else:
    print(s)


Measured memory_bytes: 13920
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define MOD 1000000007
#define INF 1e9+7
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;

#define MAX_N 100000
#define MAX_M 100000
#define MAX_V 100
#define MAX_E 100

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

int ddx[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int ddy[] = {0, -1, 0, 1, 1, 1, -1, -1};

//--------------------------



int main() {

  int n;
  cin >> n;

  cout << n*n*n << endl;

  return 0;
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

pub fn ncr(n: u64, r: u64) -> u64 {
    (n - r + 1..n + 1).product::<u64>() / (1..r + 1).product::<u64>()
}

use std::collections::HashMap;

fn main() {
    input! {
        n: usize,
        ss: [chars;n]
    }
    let march: Vec<char> = "MARCH".chars().collect();
    let v: Vec<char> =
        ss.iter().map(|s| s[0]).filter(|c| march.iter()
          .any(|m| *m == *c)).collect();
    let mut m: HashMap<char,u64> = HashMap::new();
    for x in v {
        *m.entry(x).or_insert(0) += 1;
    }
    let mut cnt = 0;
    let v: Vec<u64> = m.iter().map(|t| *t.1).collect();
    for (i,a) in v.iter().enumerate() {
        for (j,b) in v.iter().enumerate() {
            for (k,c) in v.iter().enumerate() {
                if i != j && j != k && k != i{
                    cnt += a * b * c;
                }
            }
        }
    }
    println!("{}", cnt / 6);
}


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

namespace ABC133C
{
    class Program
    {
        static long mod = 2019;
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            long L = long.Parse(input[0]);
            long R = long.Parse(input[1]);
            if (R - L >= mod)
            {
                Console.WriteLine(0);
            }
            else
            {
                long min = mod;

                long i = L % mod;
                long j = R % mod;
                long ans = mod;
                for (long m = i; m <= j - 1; m++)
                {
                    for (long k = i + 1; k <= j; k++)
                    {
                        ans = (m * k) % mod;
                        min = (long)Math.Min(min, ans);
                    }
                }
                Console.WriteLine(min);
            }
        }
    }
}


Measured memory_bytes: 13140
/* *
 *
 * Author: Hamkor
 *
 * */
 
#include <bits/stdc++.h>

using namespace std;

/* * * *   * * *   	* * * */
typedef long long ll;
const int oo = 1e9;
const ll mod = 100000000;
typedef complex<ll> P;
#define X real()
#define Y imag()
/* * * *   * * *   	* * * */

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int h, w; cin>>h>>w;
	int a[h+1][w+1];
	vector<vector<int>> b;
	for (int i=1; i<=h; ++i) for (int j=1; j<=w; ++j) cin>>a[i][j];
	for (int i=1; i<=h; ++i){
		for (int j =1; j<w; ++j) {
			if (a[i][j]%2){
				b.push_back({i, j, i, j + 1});
				a[i][j+1]++;
			}
		}
	}
	for (int i=1; i<h; ++i) {
		if (a[i][w]%2) {
			b.push_back({i, w, i+1, w});
			a[i+1][w]++;
		}
	}
	cout<<(int)b.size()<<endl;
	for (auto i: b) for (int j=0; j<4; ++j) cout<<i[j]<<" \n"[j+1==4];
	return 0;
}



Measured memory_bytes: 10032
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int read()
{
	int k=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
int n;
char s[200055];
int getw(int pos)
{
	if(pos>n) return pos;
	if(s[pos]=='W') return pos;
	return getw(pos+1);
}
int getr(int pos)
{
	if(!pos) return pos;
	if(s[pos]=='R') return pos;
	return getr(pos-1);
}
int main()
{
	n=read();scanf("%s",s+1);
	int ans=0;
	int	L=getw(0),R=getr(n+1);
	while(R>L)
	{
		if(L==0||R==n+1)
			break;
		swap(s[L],s[R]);ans++;
		L=getw(L+1);
		R=getr(R-1);
		
	}
	R=getr(n+1);
	for(int i=1;i<=R;i++)
		if(s[i]=='W')
			ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3448
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

ll dp[110][2][4];

int main(){
  string S;
  cin>>S;
  int N=S.size();
  int K;
  cin>>K;

  dp[0][0][0]=1;
  for(int i=0;i<N;i++){
    for(int k=0;k<2;k++){
      for(int l=0;l<=K;l++){
        for(int m=0;m<2;m++){
          if(m==0){
            int nk=k,nl=l;
            if(S[i]-'0'!=0) nk=1;
            dp[i+1][nk][nl]+=dp[i][k][l];
          }else{
            for(int p=1;p<=9;p++){
              int nk=k,nl=l+1;
              if(nl>K) continue;
              if(k==0&&S[i]-'0'>p) nk=1;
              if(k==0&&S[i]-'0'<p) continue;
              dp[i+1][nk][nl]+=dp[i][k][l];
            }
          }
        }
      }
    }
  }

  ll ans=0;
  rep(k,2) ans+=dp[N][k][K];
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
<?php
// Your code here!
    $num = intval(trim(fgets(STDIN)));
    
    $hour = floor($num / 3600);
    
    $minutes = floor(($num - ($hour*3600))/60);
    
    $second = $num - ($hour*3600) - $minutes*60;
    
    echo $hour.":".$minutes.":".$second."\n";
    
?>


Measured memory_bytes: 9188
use std::io::*;
use std::str::FromStr;
use std::collections::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let st: String = read();
    let mut s = st.chars().collect::<VecDeque<_>>();
    let q: u32 = read();

    let mut reverse = -1;

    for _ in 0..q {
        let t: u32 = read();

        if t == 1 {
            reverse *= -1;
        } else {
            let f: u32 = read();
            let mut c: String = read();
            for c in c.chars() {
                if f == 1 {
                    if reverse == -1 {
                        s.push_front(c);
                    } else {
                        s.push_back(c);
                    }
                } else {
                    if reverse == 1 {
                        s.push_front(c);
                    } else {
                        s.push_back(c);
                    }
                }
            }
        }
    }

    let s = if reverse == 1 {
        s.into_iter().rev().collect::<String>()
    } else {
        s.into_iter().collect::<String>()
    };

    println!("{}", s);
}


Measured memory_bytes: 6396
def main():
    S = input()
    first = int(S[:2])
    latter = int(S[2:])
    yymm = True
    mmyy = True
    if first > 12 or first == 0:
        mmyy = False
    if latter > 12 or latter == 0:
        yymm = False
    if mmyy and yymm:
        print("AMBIGUOUS")
    elif mmyy:
        print("MMYY")
    elif yymm:
        print("YYMM")
    else:
        print("NA")
main()

Measured memory_bytes: 3060
"""

なるべく各操作における奇数文字目に1をいれる
最後にたす数は確定

左端が1の時、最初に入れない理由はない
最初に必要な1を全部入れない理由、あるか？
なさそう

あとはどう0を入れていくか
1のうち、いくつが空数番目・いくつが奇数番目にいあるかを考える

0を入れると、それ以降の1の偶奇がひっくり返る
差は高々1
右端は毎回ひっくり返されるので考えなくていい
2番目は、右端で1回だけ延長できる
3番目は、2回延長できる

"""

T = input()

ans = 0
onum = 0

for i in T:

    if i == "1":
        onum += 1
        ans += (onum+1)//2

odd = []
eve = []

nodd = 0
neve = 0

#print (ans)

for i in range(len(T)-1,-1,-1):

    if T[i] == "0":
        odd.append(nodd)
        eve.append(neve)
        nodd = 0
        neve = 0
    else:
        if i % 2 == 0:
            nodd += 1
        else:
            neve += 1

#print (odd,eve)
ans += nodd * ( len(T) - onum )
#print (ans)

for i in range(len(odd)):

    now = 0
    if i == 0:
        now += len(odd)//2 * eve[i]
        now += (len(odd) - len(odd)//2) * odd[i]
    else:
        now += (len(odd)-i)//2 * eve[i]
        now += ((len(odd)-i) - (len(odd)-i)//2 ) * odd[i]
        rem = len(odd) - ( (len(odd)-i)//2 +(len(odd)-i) - (len(odd)-i)//2)
        
        now += rem * max(eve[i],odd[i])

    #print (now)
    ans += now

print (ans)


Measured memory_bytes: 95064
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 998244353
#define mo 998244353
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;

ll comb(ll N_, ll C_) {
	const int NUM_ = 400001;
	static ll fact[400002], factr[400002], inv[400002];
	if (fact[0] == 0) {
		inv[1] = fact[0] = factr[0] = 1;
		for (int i = 2; i <= NUM_; ++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i = 1; i <= NUM_; ++i) fact[i] = fact[i - 1] * i%mo, factr[i] = factr[i - 1] * inv[i] % mo;
	}
	if (C_<0 || C_>N_) return 0;
	return factr[C_] * fact[N_] % mo*factr[N_ - C_] % mo;
}
ll modpow(ll a, ll n = mo - 2) {
	ll r = 1;
	while (n) r = r * ((n % 2) ? a : 1) % mo, a = a * a%mo, n >>= 1;
	return r;
}

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

	int N, A, B, K;
	cin >> N >> A >> B >> K;

	int ans = 0;
	eFOR(i, 0, N) {
		double y = (double)(K - A * i) / B;
		int a;
		if (y < 0)continue;
		
		if (ceil(y) == floor(y)) {
			a = y;
			ans += comb(N, i)*comb(N, a);
			ans %= mod;
			
		}
	}

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



Measured memory_bytes: 9600