akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int INF=1e10;
int MOD=1e9+7;
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
}
int kurai(int a,int b){
  int m=pow(10,b),n=pow(10,b-1);
  return (a%m)/n;
}
int ketawa(int a){
  int k=0;
  rep(i,keta(a)){
  k+=kurai(a,i+1);
  }
  return k;
}
int gcd(int a,int b){
  if(a%b==0)
    return b;
  return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
int mid(int a,int b,int c){
  vector<int> k(3);
  k[0]=a;k[1]=b;k[2]=c;
  sort(all(k));
  return k[1];
}
bool sosuu(int a){
  bool b=1;
  if(a<=1)
    return 0;
  else{
  rep1(i,sqrt(a)-1){
  if(a%(i+1)==0)
  b=0;
  }
  return b;
  }
}
int modpow(int a,int b,int m=MOD){
 if(!b)return 1; if(b&1)return modpow(a,b-1,m)*a%m;
 int memo = modpow(a,b>>1,m);
 return memo*memo%m;
}
int fact_mod(int n) {
    int f=1; 
for(int i=2;i<n+1;i++) f=f*(i%MOD)% MOD;
    return f;
}
int mod_pow(int x,int n) {
    int res=1;
    while(n>0){
        if(n&1) res=(res*x)%MOD; 
        x=(x*x)%MOD;        
n>>=1; 
    }
    return res;
}
int c_mod(int n, int r) {
    if(r>n-r) r=n-r;
    if(r==0) return 1;
    int a=1;
    rep(i,r) 
a=a*((n-i)%MOD)%MOD;
    int b=mod_pow(fact_mod(r), MOD-2);
    return (a%MOD)*(b%MOD)%MOD;
}
signed main(){
  int a,b,c;
  cin>>a>>b>>c;
  vector<int> d(b);
  rep(i,b)
    cin>>d[i];
  int f=0;
  rep(i,b){
  if(d[i]>c)
    f++;
  }
    out(min(b-f,f));
}


Measured memory_bytes: 256
import sys
import time
#1.2 2.8 4.12 1.5 3.0 4.5
for line in sys.stdin:
    a1,b1,c1,a2,b2,c2 = map(float,line.split())
    i=0
    x = (c1*b2-c2*b1) / (a1*b2-a2*b1)
    y = (a1*c2-a2*c1) / (a1*b2-a2*b1)
    if "-0" in str(x):
        x = 0.0
    print "%.3f %.3f"%(x,y)

Measured memory_bytes: 6308
from math import gcd

k = int(input())
cache = {}
dp = [-1] * (k + 1)
ans = 0

for x in range(1, k + 1):
    for y in range(1, k + 1):
        xy = gcd(x, y)
        if dp[xy] != -1:
            ans += dp[xy]
        else:
            tmp = 0
            for z in range(1, k + 1):
                tmp += gcd(xy, z)
            ans += tmp
            dp[xy] = tmp
print(ans)


Measured memory_bytes: 9220
#include<iostream>
using namespace std;
//int max(int a,)
int bm(int a[])
{
  int max=0,m,i;
  for(i=0;i<100005;i++)
  {
    if(a[i]>max)max=a[i];
  }
  return max;
}
int main()
{
  int n,i,a[100005]={0},x;
  cin>>n;
  for(i=0;i<n;i++)
  {
    cin>>x;
    a[x-1]++;a[x]++;a[x+1]++;
  }
  cout<<bm(a)<<endl;
  return 0;
}


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

int main (void)
{
    int n,k,i,j;
    int ary[10]={0};
    int nan;
    scanf("%d %d",&n,&k);
    for(i=0;i<k;i++)
    {
        scanf("%d",&nan);
        ary[nan]=1;
    }
    for(i=n;i<=10*n;i++)
    {
        char s[6];
        int key=1;
        sprintf(s,"%d",i);
        for(j=0;j<strlen(s);j++)
        {
            if(ary[s[j]-'0'])
            {
                key=0;
                break;
            }
        }
        if(key)
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 1708
n = int(input())
S = input()
"""
)))((()())
-3  -1  
左に何個、右に何個
"""
l = 0
r = 0
prev = ")"

for s in S:
    if prev == ")" and s == ")":
        if r > 0:
            r -= 1
        else:
            l += 1
    elif prev == ")" and s == "(":
        r += 1
    elif prev == "(" and s == ")":
        r -= 1
    elif prev == "(" and s == "(":
        r += 1
    # print(s,l,r)
    prev = s
ans = "("*l + S + ")"*r
# print(l,r)
print(ans)


Measured memory_bytes: 3064
#include <stdio.h>

int main(){
    int n, n2 = 1000, troco = 0;
    scanf("%d", &n);
    if(n <= 1000){
        troco = 1000 - n;
        printf("%d", troco);
    }else{
       for(;;){
           n2 +=1000;
           if(n <= n2){
               troco = n2 - n;
               printf("%d", troco);
               break;
           }
       }
    }
        
    

    return 0;
}

Measured memory_bytes: 1712
#include <cstdio>

using namespace std;

void trace(int A[], int N) {
  for (int i = 0; i < N; i++) {
    if (i > 0) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

void insertionSort(int A[], int N) {
  for (int i = 0; i < N; i++) {
    int v = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > v) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
    trace(A, N);
  }
}

int main() {
  int N;
  scanf("%d", &N);
  int A[100];
  for (int i = 0; i < N; i++) scanf("%d", &A[i]);

  insertionSort(A, N);
}

Measured memory_bytes: 2712
#include<bits/stdc++.h>
#define EM 1000000
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
LL LINF = 1e18;
int INF = 1e9;
LL mod = 1e9+7;
using vint = vector<int>;
using vLL = vector<LL>;
using vvint = vector<vector<int>>;
using vvLL = vector<vector<LL>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    int N;
    cin >> N;
    vector<int> h(N);
    for(int i =0;i < N;i++) cin >> h[i];
    int ans = 0;
    int cnt = 0;
    for(int i = 0;i < N-1;i++){
        if(h[i] >= h[i+1]){
            cnt++;
            if(i == N-2)    ans = max(ans, cnt);
        }
        else {
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;

int		main(void)
{
	map<string, string> W;
	W["Sunny"] =  "Cloudy";
	W["Cloudy"] = "Rainy";
	W["Rainy"] = "Sunny";
	string S;

	cin >> S;
	cout << W[S] << endl;
}



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

using namespace std;

using ll = long long;


int main() {
    vector<vector<ll>> cnt(10, vector<ll>(10, 0));
    ll N;
    cin >> N;
    for (ll i = 1; i <= N; i++) {
        string I = to_string(i);
        ll msd, lsd;
        msd = I[0] - '0';
        lsd = I[I.length() - 1] - '0';
        // cout << msd << ", " << lsd << endl;
        cnt[msd][lsd]++;
    }

    ll ans = 0;
    for (int i = 0; i <= 9; i++) {
        for (int j = 0; j <= 9; j++) {
            ans += cnt[i][j] * cnt[j][i];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import itertools

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

A_list = list(itertools.combinations_with_replacement(range(1,m+1),n))

ans = 0
for A in A_list:
    sum = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            sum += d
    ans = max(ans, sum)

print(ans)

Measured memory_bytes: 21476
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}


ll modpow(ll a,ll b){
    ll ret = 1;
    while(b>0){
        if(b&1)ret = (ret*a)%MOD;
        a = (a*a)%MOD;
        b = b>>1;
    }
    return ret;

}
int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> nk(k+1,0);
    ll ans = 0;
    for(ll i=k;i>=1;i--){
        ll s = k/i;
        ll gcds = modpow(s,n);
        ll snext = i*2;
        ll next = 3;

        while(snext<=k){
            gcds-=nk[snext];
            if(gcds<0)gcds+=MOD;
            snext=next*i;
            next++;
        }

        ans+=gcds*i;
        ans%=MOD;
        nk[i]=gcds;

    }

    cout<<ans<<endl;






return 0;
}


Measured memory_bytes: 3564
#include <iostream>

typedef long long ll;
using namespace std;

ll dp[1001][1001];

ll solve(ll n, ll k, ll m) {
  dp[0][0] = 1;
  for(int i=0;i<=n;++i) {
    for(int j=1;j<=k;++j) {
      if (i<j) {
        dp[i][j] = dp[i][j-1];
      }
      else {
        dp[i][j] = (dp[i][j-1] + dp[i-j][j]) % m;
      }
    }
  }
  return dp[n][k];
}

int main() {
  ll n,k,mod=1e9+7;
  cin>>n>>k;
  cout<<solve(n,k,mod)<<endl;
  return 0;
}


Measured memory_bytes: 10916
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

signed main()
{
    int a, b;
    cin >> a >> b;
    rep(i, 3)
    {
        if (i + 1 != a && i + 1 != b) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
use std::io;

fn read_grid() -> Vec<Vec<i32>> {
    //! load stdio input like below.
    //! ```
    //! 2
    //! 2 3
    //! 4 5
    //! ```
    let mut line = String::new();
    let mut inputs = Vec::<Vec<char>>::new();
    io::stdin().read_line(&mut line).unwrap();
    let n = line.trim().parse::<i32>();
    line.clear();
    io::stdin().read_line(&mut line).unwrap();
    let first_line: Vec<i32> = line
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<i32>().unwrap())
        .collect();
    line.clear();
    io::stdin().read_line(&mut line).unwrap();
    let second_line: Vec<i32> = line
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<i32>().unwrap())
        .collect();
    vec![first_line, second_line]
}

fn solve(grid: Vec<Vec<i32>>) -> i32 {
    let mut max_all = 0;
    for k in 1..(grid[0].len() + 1) {
        let start = grid[0][0];
        let first_sum: i32 = grid[0][..k].iter().sum();
        let second_sum: i32 = grid[1][(k - 1)..].iter().sum();
        let sum = first_sum + second_sum;

        if sum > max_all {
            max_all = sum;
        }
    }
    let first_sum: i32 = grid[0].iter().sum();
    let second_sum: i32 = grid[1][grid[0].len() - 1];
    let sum = first_sum + second_sum;
    if sum > max_all {
        max_all = sum;
    }
    return max_all;
}

fn main() {
    let inputs = read_grid();
    let res = solve(inputs);
    println!("{}", res);
}


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

using namespace std;

int main()
{
  char S[256];
  
  scanf("%s",S);
  
  if( strstr(S,"RRR") ){
    printf("3\n");
  }
  else if( strstr(S,"RR") ){
    printf("2\n");
  }
  else if( strstr(S,"R") ){
    printf("1\n");
  }
  else{
    printf("0\n");
  }
  
  return 0; 
}

Measured memory_bytes: 3652
n = gets.to_i
min = last = gets.to_i
profits = []
(n-1).times{
  current = gets.to_i
  profits<<(current-min) if (current > last) || (profits.bsearch{|i| i >= 0} == nil)
  min = current if (current < min)
  last = current
}
puts profits.max

Measured memory_bytes: 9688
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;

int main() {
	int a, b; cin >> a >> b;
	if (b%a == 0) {
		cout << a + b << endl;
	}
	else {
		cout << b - a << endl;
	}
}

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

#ifdef MYDEBUG
#define dbp(x) cout<<#x<<": "<<x<<endl
#define dbp2(x,y) cout<<#x<<","<<#y<<": "<<x<<","<<y<<endl
#define dbp3(x,y,z) cout<<#x<<","<<#y<<","<<#z<<": "<<x<<","<<y<<","<<z<<endl
#define dbp4(w,x,y,z) cout<<#w<<","<<#x<<","<<#y<<","<<#z<<": "<<w<<","<<x<<","<<y<<","<<z<<endl
#else
#define dbp(x)
#define dbp2(x,y)
#define dbp3(x,y,z)
#endif
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define all(x) x.begin(), x.end()
#define rep(i, from, to) for(int i=from; i<to; ++i)

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	out << "[";
	size_t last = v.size() - 1;
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i];
		if (i != last)
			out << ",";
	}
	out << "]";
	return out;
}

typedef struct state state;
const int maxn = 110;
int s[maxn + maxn];

int sum1(int n) {
	int x = 0;
	for (int i = 0; i < n; ++i) {
		x += s[i];
	}
	return x;
}
int sum2(int n, int m) {
	int x = 0;
	for (int i = n; i < n + m; ++i) {
		x += s[i];
	}
	return x;
}

void solve() {
	int n, m;
	while (cin >> n >> m, (n || m)) { //n||m :
		int a = 0, b = 0;
		for (int i = 0; i < n + m; i++) {
			cin >> s[i];
		}
		a = 100000000;
		b = 100000000;
		bool hasAnswer = false;
		for (int i = 0; i < n; i++) {
			for (int j = n; j < n + m; ++j) {
				swap(s[i], s[j]);
				//テ」ツδ?」ツつァテ」ツδε」ツつッ
				int s1 = sum1(n);
				int s2 = sum2(n, m);
				if (s1 == s2) {
					hasAnswer = true;
					//テ」ツ??」ツ?セテァツ卍コティツヲツ凝」ツ?療」ツ?淌ァツュツ氾」ツ?暗」ツ?ッi,j
					//a,-i, b<-j
					//a+b>i+j
					if (a + b > s[i] + s[j]) {
						a = s[i];
						b = s[j];
					}
				}
				swap(s[i], s[j]);
			}
		}
		if (hasAnswer) {
			swap(a, b);
			cout << a << " " << b << endl;
		} else {
			cout << -1 << endl;
		}
	}
}

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

Measured memory_bytes: 3068
#include<iostream>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++)
#define MAX 100
#define INFTY (1<<21)
int n, m, G[MAX][MAX], E[MAX*MAX];

int eprim( int base ){
    int d[MAX];
    bool visited[MAX];
    rep(i, n){
	d[i] = INFTY;
	visited[i] = false;
    }
    d[0] = 0;
    int cnt = 0;
    int ans = 0;

    while(1){
	int minv = INFTY;
	int u;
	rep(i, n){
	    if ( !visited[i] && minv > d[i]){
		minv = d[i]; u = i;
	    }
	}
	if ( minv == INFTY ) break;
	if ( u != 0 && ans < minv ) ans = minv;
	cnt++;
	visited[u] = true;

	rep(v, n){
	    if ( visited[v] || G[u][v] == INFTY ) continue;
	    if ( base > G[u][v] ) continue;
	    if ( d[v] > G[u][v] - base ){
		d[v] = G[u][v] - base;
	    }
	}
    }
    if ( cnt != n ) return INFTY;
    return ans;
}

void compute(){
    int minv = INFTY;
    rep(i, m){
	minv = min ( minv, eprim(E[i]) );
    }
    if ( minv == INFTY ) cout << -1 << endl;
    else cout << minv << endl;
}

main(){
    int s, t, e;
    while( cin >> n >> m ){
	if ( n == 0 && m == 0 ) break;
	rep(i, n) rep(j, n) G[i][j] = INFTY;
	rep(i, m){
	    cin >> s >> t >> e;  s--; t--;
	    G[s][t] = G[t][s] = E[i] = e;
	}
	compute();
    }
}

Measured memory_bytes: 920
using System;
using System.Diagnostics;
using System.IO;

namespace AtCoder.ABC109 {
    class A {
        static void Main() => CustomMain();

        static void Solve() {
            var a = ReadIntArray();

            WriteAnswer(IsOdd(a[0] * a[1]) ? "Yes" : "No");
        }

        static void CustomMain() {
#if DEBUG
            // ファイルからテストケースを読み込む
            global::Common.ChangeStdIn();
            // 時間計測
            var stopwatch = new Stopwatch();
            stopwatch.Start();
#endif
            // 出力高速化
            var streamWriter = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            Console.SetOut(streamWriter);
            // 回答
            Solve();
#if DEBUG
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);
#endif
            Console.Out.Flush();
        }

        static string ReadString() => Console.ReadLine().Trim();
        static int ReadInt() => int.Parse(ReadString());
        static long ReadLong() => long.Parse(ReadString());
        static float ReadFloat() => float.Parse(ReadString());
        static double ReadDouble => double.Parse(ReadString());

        static string[] ReadStringArray() => ReadString().Split(' ');
        static int[] ReadIntArray() => Array.ConvertAll(ReadString().Split(' '), int.Parse);
        static long[] ReadLongArray() => Array.ConvertAll(ReadString().Split(' '), long.Parse);
        static float[] ReadFloatArray() => Array.ConvertAll(ReadString().Split(' '), float.Parse);
        static double[] ReadDoubleArray() => Array.ConvertAll(ReadString().Split(' '), double.Parse);

        static T TypeConversion<T>(string s) {
            if (typeof(T) == typeof(int)) {
                return (T) Convert.ChangeType(int.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(long)) {
                return (T) Convert.ChangeType(long.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(double)) {
                return (T) Convert.ChangeType(double.Parse(s), typeof(T));
            } else {
                return (T) Convert.ChangeType(s, typeof(T));
            }
        }

        static void ReadMulti<T, U>(out T a, out U b) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
        }

        static void ReadMulti<T, U, V>(out T a, out U b, out V c) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
            c = TypeConversion<V>(str[2]);
        }

        static void WriteAnswer(object ans) => Console.WriteLine(ans);

        static bool IsOdd(long num) {
            return (num & 1) == 1;
        }

        static bool IsEven(long num) {
            return (num & 1) == 0;
        }
    }
}

Measured memory_bytes: 11092
s=input()
q=int(input())
mae=''
ato=''
ten=0

for i in range(q):
  ss=input()
  if ss[0]=='1':
    ten+=1
    ten%=2
  else:
    t,f,c=ss.split()
    if f=='1':
      if ten==0:
        mae+=c
      else:
        ato+=c        
    else:
      if ten==0:
        ato+=c
      else:
        mae+=c
mae=mae[::-1]
s=mae+s+ato
if ten==1:
  s=s[::-1]
print(s)
    

Measured memory_bytes: 4304
#include <iostream>

using namespace std;

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

int main()
{
    int w, h;
    cin >> h >> w;
    char mass[50][50];
    int ans[50][50];
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> mass[i][j];
        }
    }

    // init
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            ans[i][j] = 0;
        }
    }

    // height
    for (int i = 0; i < h; i++)
    {
        // wide
        for (int j = 0; j < w; j++)
        {
            // mass
            for (int k = 0; k < 8; k++)
            {
                int nei_x = i + dx[k];
                int nei_y = j + dy[k];
                if (nei_x < 0 || h <= nei_x)
                    continue;
                if (nei_y < 0 || w <= nei_y)
                    continue;
                if (mass[nei_x][nei_y] == '#')
                {
                    ans[i][j]++;
                }
            }
        }
    }

    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if (mass[i][j] == '#')
                cout << '#';
            else
                cout << ans[i][j];
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3212
#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(ll);
typedef long long ll;

using namespace std;

ll solve(ll n,ll wt[],ll val[],ll target)
{
	ll i,k,ans,j;
    ll dp[target+1][n+1];

    for(i=0;i<target+1;i++)
    {
        for(j=0;j<n+1;j++)
        {
            if(i==0||j==0)dp[i][j]=0;

           else if(wt[j-1]<=i)
            dp[i][j]=max(val[j-1]+dp[i-wt[j-1]][j-1],dp[i][j-1]);
            else
            {
                dp[i][j]=dp[i][j-1];
            }
            
        }
    }
    return dp[target][n];
}

int main()
{

    ll n,max_wt;
    cin>>n>>max_wt;
    ll wt[n],val[n];
    for(ll i=0;i<n;i++)cin>>wt[i]>>val[i];

    cout<<solve(n,wt,val,max_wt)<<endl;

}

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

using namespace std;

#define F first
#define S second
#define modulo ll (1e9 + 7)

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

void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
}

const int N = 55, M = 3e3, OO = 0x3f3f3f3f;
const ll llOO = 0x3f3f3f3f3f3f3f3f;

int main(){
    init();

    string s;   cin >> s;

    int ans = 0;
    for(int i = 1;i < s.size();i++)
        ans += s[i] != s[i - 1];

    cout << ans;
}

Measured memory_bytes: 512
def main():
	N, K = map(int, input().split())
	DIV = 10**9+7
	sqrtn = int(N**0.5)
	ans = 1
	s = []
	for i in range(1, sqrtn+1):
		s.append(i)
		if i < N//i:
			s.append(N//i)
	s.sort()

	r = []
	for i in range(len(s)-1):
		left = N//s[i+1]
		right = N//s[i]
		r.append(right-left)
	r.append(1)

	m = len(s)
	mp = {}
	for i in range(m):
		mp[s[i]] = i

	dp = [[0 for _ in range(m)] for _ in range(K+1)]
	dp[0][mp[N]] = 1
	for i in range(K):
		for j in range(m-2, -1, -1):
			dp[i][j] += dp[i][j+1]
			dp[i][j] %= DIV
		for j in range(m):
			nj = mp[N//s[j]]
			dp[i+1][j] += dp[i][nj]*r[j]%DIV
			dp[i+1][j] %= DIV

	ans = 0
	for j in range(m):
		ans += dp[K][j]
		ans %= DIV
	print(ans)


if __name__ == '__main__':
	main()

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

int main(int argc, const char * argv[]) {
    long long a,b,n,n1,n2,n3,n4,n5,nsum,sum=0;
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        n1=i%10;
        n2=i%100/10;
        n3=i%1000/100;
        n4=i%10000/1000;
        n5=i%100000/10000;
        nsum=n1+n2+n3+n4+n5;
        if(nsum>=a&&nsum<=b){sum=sum+i;
            //cout<<i<<" "<<n1<<" "<<n2<<" "<<n3<<" "<<n4<<" "<<n5<<endl;
        }
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
/*
 * B.cpp
 *
 *  Created on: 2017/05/27
 *      Author: aihara
 */

#define MYDEBUG
#include <bits/stdc++.h>

#ifdef MYDEBUG
#define dbp(x) cout << "#x" << ": " << x << endl;
#else
#define dbp(x)
#endif
#define ll long long
using namespace std;

const int maxh = 60;
int w, h;
int c[maxh][maxh];
int di[9] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dj[9] = { -1, 0, 1, -1, 1, -1, 0, 1 };

int ans = 0;
int dfs(int i, int j) {
	if (c[i][j] != 1) {
		return 0;
	}
	c[i][j] = -1;
	for (int k = 0; k < 9; ++k) {
		int ni = i + di[k], nj = j + dj[k];
		if (0 <= ni && ni < h && 0 <= nj && nj < w && c[ni][nj] == 1) {
			dfs(ni, nj);
		}
	}
	return 1;
}

int main() {
	while (cin >> w >> h, w || h) {
		ans = 0;
		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < w; ++j) {
				cin >> c[i][j];
			}
		}
		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < w; ++j) {
				ans += dfs(i, j);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3068
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            WillReturn.Add("G W Y P Y W");
            //Four
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9");
            WillReturn.Add("G W W G P W P G G");
            //Three
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8");
            WillReturn.Add("P Y W G Y W Y Y");
            //Four
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string[] SArr = InputList[1].Split(' ');

        Console.WriteLine(SArr.Distinct().Count() == 3 ? "Three" : "Four");
    }
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll ab, bc, ca; cin >> ab >> bc >> ca;
    cout << ab * bc / 2 << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3604
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    B = [inf] + LIST() + [inf]
    sumv = 0
    for i in range(N):
        sumv += min(B[i], B[i+1])
    print(sumv)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int a[4];
	cin >> a[0] >> a[1] >> a[2] >> a[3];
	sort(a, a + 4);
	if (a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}

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

using namespace std;

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

	string first = "";

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		first += to_string(temp);
	}

	string second = "";

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		second += to_string(temp);
	}

	string perm = first;

	sort(perm.begin(), perm.end());
	int index = 1;
	int firstRes = 0;
	int secondRes = 0;

	do {
		if (perm == first) {
			firstRes = index;
		}
		if (perm == second) {
			secondRes = index;
		}
		index++;
	} while (next_permutation(perm.begin(), perm.end()));


	cout << abs(firstRes - secondRes);
}

Measured memory_bytes: 256
from collections import deque
s = input()
q = int(input())
flag = True
d = deque(s)
for i in range(q):
    inp = input()
    if inp == '1':
        flag = not flag

    else:
        _, f, c = map(str, inp.split())
        if f == '1':
            if flag:
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if flag:
                d.append(c)
            else:
                d.appendleft(c)

if flag:
    while(d):
        t = d.popleft()
        print(t, end='')
else:
    while(d):
        t = d.pop()
        print(t, end='')


Measured memory_bytes: 94552
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define PI 3.14159265358979323846
#define INF 1 << 30

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

int main(void) {
	int num, m, i, j, k, ans;
	cin >> num >> m;
	ans = num;
	vector<vector<int>> d(num, vector<int>(m));
	vector<int> p(num, 0), ok(m + 1, 1);
	rep(i, num) {
		rep(j, m)
			cin >> d[i][j];
	}
	rep(k, m - 1) {
		int s, ma = 0;
		vector<int> a(m + 1, 0);
		rep(i, num) {
			if (ma < ++a[d[i][p[i]]]) {
				ma = a[d[i][p[i]]];
				s = d[i][p[i]];
			}
		}
		chmin(ans, ma);
		ok[s] = 0;
		rep(i, num) {
			while (!ok[d[i][p[i]]])
				p[i]++;
		}
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 3936
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int digit_sums(int N){
    int res = 0;
    while(N > 0){
        res += N % 10;
        N /= 10;
    }
    return res;
}
int main(void){
    int N;
    cin >> N;
    string ans = "No";
    if(N % digit_sums(N) == 0){
        ans = "Yes";
    }
    cout << ans << endl;
}


Measured memory_bytes: 3052
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using PLL = pair<ll, ll>;
constexpr ll MOD = 1e9+7;

ll modpow(ll a, ll n){
    ll ret = 1;
    while(n > 0){
        if(n & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return ret;
}

int main(){
    int n;
    cin >> n;
    map<PLL, PLL> mp;
    ll zero = 0;
    for(int i = 0; i < n; i++){
        ll l, r;
        cin >> l >> r;
        if(r < 0){
            l = -l;
            r = -r;
        }
        if(r == 0 && l == 0) zero++;
        else{//0<= sita <= 2/pi にしたい
            ll dv = abs(__gcd(l, r));
            if(l == 0) mp[make_pair(0, 1)].first++;
            else if( r == 0) mp[make_pair(0, 1)].second++;
            else if(l > 0){
                mp[make_pair(l/dv, r/dv)].first++;
            }
            else mp[make_pair(r/dv, -l/dv)].second++;
        }
    }

    ll ans = 1;
    for(auto p : mp){
        ans = ans * (modpow(2, p.second.first) + modpow(2, p.second.second) - 1) % MOD;
    }
    cout << (ans - 1 + zero + MOD) % MOD << endl; // ansの一つも入れない場合を除く、ansとzeroは完全に独立で一緒にはいれられない
}

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

#define FORS(i, j, k, step) for (int i=j; i<k; i+=step)
#define FOR(i, j, k) for (int i=j; i<k; i++) 
#define RFORS(i, j, k, step) for (int i=j; i>=k; i-=step)
#define RFOR(i, j, k) for(int i=j; i>=k; i--)
#define REP(i, k) for(int i = (0); i < (k); i++ ) 
#define RREP(i, k) for(int i = (k); i >= (0); i-- )
 
#define ALL(cont) cont.begin(), cont.end()
#define RALL(cont) cont.begin(), cont.end()
#define FOREACH(it, l) for(auto it=l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define RESET(a, b) memset(a, b, sizeof(a))
#define INF (int)MAX_INT
#define EPS (int)1e-9
#define PI acos(-1)
#define MOD 1000000007
#define run using
#define the namespace
#define prog std
 
run the prog;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<piii> viii;
typedef long long int32;
typedef unsigned long long uint32;
typedef long long int int64;
typedef unsigned long long int uint64;
 
template <class T>
    T sqr(T val) {
        return val * val;
    }
 
template<typename T, typename U> 
static inline void amin(T &x, U y) 
{ 
    if (y < x) 
        x = y; 
} 
  
// call by reference is used in x 
template<typename T, typename U> 
static inline void amax(T &x, U y) 
{ 
    if (x < y) 
        x = y; 
} 

/* To find max and min value in array.
for (auto const &val: array) 
  
        // Same as max_val = max (max_val, val) 
        // Same as min_val = min (min_val,val) 
        amax(max_val, val), amin (min_val, val);
//Then in main()
int max_val = 0, min_val = 1e5; 
 */
int32 gcd(int32 a, int32 b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);
} 
void solve() {
    /* Solution code goes here */
    int32 n ,sum=0;
    cin>>n;
    int has[100001];
    RESET(has,0);
    REP(i,n)
    {
        int32 x;
        cin>>x;
        sum+=x;
        has[x]++;
    }
    int32 q;
    cin>>q;
    // REP(i,n)
    // {
    //     cout<<has[i]<<" ";
    // }
    REP(i,q)
    {
        int32 a , b;
        cin>>a>>b;
        //cout<<has[a]<<" "<<has[b]<<endl;
        int32 d = has[a]*b - has[a]*a;
        sum += d;
        int32 temp = has[a];
        has[a] = 0;
        has[b] += temp;
       // cout<<has[a]<<" "<<has[b]<<endl;
       cout<<sum<<endl;
    }
}
 
int main() {
    std::ios_base::sync_with_stdio(false);
    int32 TC = 1;
    //cin >> TC;
    
    //cin.ignore();
    while(TC--)
    {
        solve();
    }
}

Measured memory_bytes: 4032
s = input()
rev_s = s[::-1]

key = "keyence"
label = [[key[:i], key[i:][::-1]] for i in range(len(key)+1)]

flag = False
for i, l in enumerate(label):
  if s[:i] == l[0] and rev_s[:len(l[1])] == l[1]:
    flag = True
    break
print("YES" if flag else "NO")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e+9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main(){
    long double l; cin >> l;
    long double volume= (l/3.0)*(l/3.0)*(l/3.0);

    cout << fixed;
    cout << setprecision(12) << volume << endl;

}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct BinaryIndexedTree{
	int n;
	vector<int>dat;
	BinaryIndexedTree(int n=0):n(n){
		dat.resize(n+1);
	}
	void add(int k,int x){
		for(k++;k<=n;k+=k&-k)dat[k]+=x;
	}
	int sum(int k){
		int ret=0;
		for(k++;k;k-=k&-k)ret+=dat[k];
		return ret;
	}
};

int Q;
int A[666666],B[666666];

signed main(){

    cin>>Q;
    string s;
    cin>>s;reverse(all(s));
    for(int i=0;i<s.size();i++)A[i]=s[i]=='1';
    cin>>s;reverse(all(s));
    for(int i=0;i<s.size();i++)B[i]=s[i]=='1';

    set<int>b;
    set<int>latte,beet;
    BinaryIndexedTree bit(666666+114);
    for(int i=0;i<666666;i++){
        bit.add(i,A[i]);
        if(B[i])b.insert(i);
        if(A[i]==1&&B[i]==1)latte.insert(i);
        if(A[i]==0&&B[i]==0)beet.insert(i);
    }
    latte.insert(-2);
    beet.insert(-1);

    while(Q--){
        char c;cin>>c;
        if(c=='Q'){
            int x=*b.rbegin();

            auto it=latte.upper_bound(x);
            it--;
            auto jt=beet.upper_bound(x);
            jt--;
            if(*it>*jt){
                cout<<bit.sum(666666)-bit.sum(x)+x+1<<endl;
            }
            else{
                cout<<bit.sum(666666)-bit.sum(x)+x<<endl;
            }
        }
        else if(c=='A'){
            int x;cin>>x;
            if(A[x]&&B[x])latte.erase(x);
            if(!A[x]&&!B[x])beet.erase(x);
            bit.add(x,-A[x]);

            A[x]^=1;
            if(A[x]&&B[x])latte.insert(x);
            if(!A[x]&&!B[x])beet.insert(x);
            bit.add(x,A[x]);
        }
        else{
            int x;cin>>x;
            if(A[x]&&B[x])latte.erase(x);
            if(!A[x]&&!B[x])beet.erase(x);
            if(B[x]==1)b.erase(x);
            else b.insert(x);

            B[x]^=1;
            if(A[x]&&B[x])latte.insert(x);
            if(!A[x]&&!B[x])beet.insert(x);
        }
    }
    return 0;
}

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

set<string> used;

void out(){
    cout << "!OUT" << endl;
    exit(0);
}

string say(string s){
    cout << "?" << s << endl << flush;
    used.insert(s);
    string ret;
    cin >> ret;
    if(s[s.length()-1] != ret[0] || used.count(ret)){
        out();
    }else{
        used.insert(ret);
    }
    return ret;
}

int main(){
    string t = say("a");
    while(true){
        string k = "";  k += t[t.length()-1];
        for(char c = 'a'; c <= 'z'; c++){
            string s = k;   s += c;
            if(used.count(s) == 0){
                t = say(s);
                break;
            }
        }
    }
}


Measured memory_bytes: 3260
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

n = int(input())
a = list(map(int, input().split()))
ans = 1001001001
for i in range(n-1):
    ans = min(ans,gcd(a[i],a[i+1]))

print(ans)


Measured memory_bytes: 14224
/*{{{*/
//#define HOME
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define F first
#define S second

template<class T> void _R(T &_x) { cin >> _x; }
void _R(int &_x) { scanf("%d", &_x); }
void _R(int64_t &_x) { scanf("%" SCNd64, &_x); }
void _R(double &_x) { scanf("%lf", &_x); }
void _R(char &_x) { scanf(" %c", &_x); }
void _R(char *_x) { scanf("%s", _x); }
template<class T, class U> void _R(pair<T, U> &_x) {_R(_x.F); _R(_x.S);}
void R() {}
template<class T, class... U> void R(T &_head, U &... _tail) { _R(_head); R(_tail...); }

template<class T> void _W(const T &_x) { cout << _x; }
void _W(const int &_x) { printf("%d", _x); }
void _W(const int64_t &_x) { printf("%" PRId64, _x); }
void _W(const double &_x) { printf("%.16f", _x); }
void _W(const char &_x) { putchar(_x); }
void _W(const char *_x) { printf("%s", _x); }
template<class T, class U> void _W(const pair<T, U> &_x) {_W(_x.F); putchar(' '); _W(_x.S);}
template<class T> void _W(const vector<T> &_x) { for (auto i = _x.begin(); i != _x.end(); _W(*i++)) if (i != _x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &_head, const U &... _tail) { _W(_head); putchar(sizeof...(_tail) ? ' ' : '\n'); W(_tail...); }
template<class T, class... U> void DB(const T &_head, const U &... _tail) {
#ifdef HOME
    W('#', _head, _tail...);
#endif
}

#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define RAN(x,n) (x).begin(), (x).begin()+(n)
#define UNIQUE(x) {sort(ALL(x)); (x).erase(unique(ALL(x)), (x).end());}

#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
//#define ITER(i,t) for (auto i = t.begin(); i != t.end(); ++i)
#define IT3(i,st,ed) for (auto i = st; i != ed; ++i)
#define IT2(i,range) IT3(i,range)

#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define MS(X, v) memset((X), (v), sizeof((X)))

template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

inline int LG (const unsigned int &_x) { return 31-__builtin_clz(_x); }  // floor: LG(x), ceil: LG(x-1)+1
/*}}}*/

string s;
int n;
vector<ll> as;

int main(){
    R(s);
    n = s.length() + 1;
    as.assign(n, 0);

    FOR(i, n-1) if(s[i] == '<'){
        as[i+1] = max(as[i+1], as[i]+1);
    }
    REPD(i, n-1, 0) if(s[i] == '>'){
        as[i] = max(as[i], as[i+1]+1);
    }

    ll ans = 0;
    ans = accumulate(ALL(as), 0LL);

    W(ans);

    return 0;
}


Measured memory_bytes: 4740
//C - Otoshidama: 
//Assunto: 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define loop(i, a, b) for(int i = a; i < b; i++)
#define loopBack(i, a, b) for(int i = a; i >= b; i--)
#define INF INT_MAX
#define LINF LLONG_MAX
#define DINF DBL_MAX
#define MAX 100005
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

int a = -1, b = -1, c = -1;
bool dp[2005][20005];

void solve(int cnt, int soma, int total, int x, int y, int z) {
    if(soma > total) return;
    if(cnt <= 0) {
        if(soma == total) {
            a = x; b = y; c = z;
        }
        return;
    }
    if(dp[cnt][soma]) return;
    solve(cnt-1, soma + 10, total, x+1, y, z);
    solve(cnt-1, soma + 5, total, x, y+1, z);
    solve(cnt-1, soma + 1, total, x, y, z+1);\
    dp[cnt][soma] = true;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    memset(dp, false, sizeof(dp));
    int n, y;
    cin >> n >> y;
    if(y % 1000 == 0) {
        y /= 1000;
        solve(n, 0, y, 0, 0, 0);
    }
    cout << a << " " << b << " " << c << "\n";
}

Measured memory_bytes: 39552
s = list(input())

last = s[0]

c = 1

ans = 0

for i in range(1, len(s)):
	if(last == s[i]):
		ans += 1
		if(last == "0"):
			last = "1"
		else:
			last = "0"
	else:
		last = s[i]
print(ans)

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

int MOD = 1000000007;

int main(){
    int N, M;
    cin >> N >> M;
    vector<bool> broken(N+1,false);
    for (int i=0;i<M;i++){
        int s;
        cin >> s;
        broken[s] = true;
    }
    // i=pまでの移動方法をdp[p]とする
    // dp[p] = 0
    // p-1が壊れていないとき dp[p] += dp[p-1]
    // p-2が壊れていないとき dp[p] += dp[p-2]
    vector<int> dp(N+1,0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i=2;i<=N;i++){        
        if (broken[i-2] == false) dp[i] += dp[i-2];
        dp[i] %= MOD;
        if (broken[i-1] == false) dp[i] += dp[i-1];
        dp[i] %= MOD;
    }
    cout << dp[N] << endl;
}

Measured memory_bytes: 640
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
man=0
prev=100
for i in range(n):
    man+=b[a[i]-1]
    if a[i]==(prev+1):
        man+=c[prev-1]
    prev=a[i]
print(man)


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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}


int main() {
  int N;
  cin >> N;
  vector< int > A(N);
  cin >> A;

  if(is_sorted(begin(A), end(A))) {
    cout << "YES" << endl;
    return 0;
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < i; j++) {
      swap(A[i], A[j]);

      if(is_sorted(begin(A), end(A))) {
        cout << "YES" << endl;
        return 0;
      }
      swap(A[i], A[j]);
    }
  }

  cout << "NO" << endl;
}







Measured memory_bytes: 256
#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	if (n == m) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}




Measured memory_bytes: 256
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial
n=int(input())
r=set()
g=set()
b=set()
s=input()
for i in range(len(s)):
	if s[i]=='R':
		r.add(i)
	elif s[i]=='G':
		g.add(i)
	else:
		b.add(i)
count=0
for i in r:
	for j in g:
		x=len(b)
		if 2*j-i in b:
			x-=1
		if 2*i-j in b:
			x-=1
		if (i+j)%2==0 and (i+j)//2 in b:
			x-=1
		count+=x
print(count)

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

set <pair<int,int>> s;
int h,w,n,x,y;
set <int> obs[200001];
int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> h >> w >> n;
	for(int i=0;i<n;i++)
	{
		cin >> x >> y;
		s.insert(make_pair(x,y));
		obs[y].insert(x);
	}

	long long int res = 1e18;
	long long int cnt = 0;
	x = 1;
	y = 1;
	bool flag = true;
	int turn = 0;
	while(1)
	{
		//cout << x << ' ' << y << '\n';
		auto it = obs[y].lower_bound(x);
		if(it==obs[y].end())
		{
			res = min(res,cnt + h  + 1 - x);
		}
		else
		{
			//cout << x << ' ' << y << ' ' << *it << ' ' << cnt << ' ' << *it - x << '\n';
			res = min(res,cnt + (*it - x));
		}
		if(turn==0)
		{
			cnt++;
			if(x==h)
			{
				if(flag==false)
				{
					break;
				}
				flag = false;
			}
			else
			{
				if(s.find(make_pair(x+1,y))!=s.end())
				{
					if(flag==false)
					{
						break;
					}
					flag = false;
				}
				else
				{
					//cnt++;
					x += 1;
					flag = true;
				}
			}
			turn = 1;
		}
		else
		{
			if(y==w)
			{
				if(flag==false)
				{
					break;
				}
				flag = false;
			}
			else
			{
				if(s.find(make_pair(x,y+1))==s.end())
				{
					y += 1;
					flag = true;
				}
				else
				{
					if(flag==false)
					{
						break;
					}
					flag = false;
				}
			}
			turn = 0;			
		}
	}

	cout << res << '\n';

	return 0;	
}


Measured memory_bytes: 28416
#include <bits/stdc++.h>
#define inf 9884857552142353

using namespace std;

int main() {


    long long S, m;
    cin >> S >> m;
    vector <long long> dp(11005, -1);
    dp[0] = 0;
    vector <long long> w (m);
    vector <long long> c (m);
    for (long long i = 0; i < m; ++i) {
        cin >> w[i] >> c[i];
    }
    for (long long i = 0; i < m; ++i) {

        for (long long j = 0; j < 11000; ++j) {
            if (w[i] <= j) {
                if (dp[j - w[i]] != -1) {
                    if (dp[j] == -1)
                        dp[j] = dp[j - w[i]] + c[i];
                    else
                        dp[j] = min(dp[j - w[i]] + c[i], dp[j]);
                }
            }
        }
    }


    long long ans = 99756745678876578;
    for (long long i = S; i < 11000; ++i) {
        if (dp[i] != -1)
            ans = min(ans, dp[i]);
    }

    cout << ans;



    return 0;
}


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ll long long
using namespace std;


int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (a + b + c >= 22) {
    cout << "bust" << endl;
  }
  else {
    cout << "win" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a=n/10;
    int b=n%1000;
    if(a/100==a%100/10&&a%100/10==a%10)
    cout<<"Yes"<<endl;
    else if(b/100==b%100/10&&b%100/10==b%10)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
}

Measured memory_bytes: 3640