akhauriyash/Code-Regression huggingface dataset:
import collections
N = int(input())
a = list(map(int,input().split()))
mod = (10**9+7)
if N%2 !=0:
    if sum(a)%2!=0 or max(a)>N or a.count(0)!=1 or len(set(a))!=N//2+1:
        print(0)
    else:
        print(2**(len(set(a))-1)%mod)
elif N%2 ==0:
    if sum(a)%2!=0 or max(a)>N or len(set(a))!=N//2:
        print(0)
    else:
        print(2**len(set(a))%mod)

Measured memory_bytes: 14196
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF (1<<31)-1
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
#define vii vector<int>
#define vll vector<long long>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
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; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

ll n, m, ans;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> n >> m;
    if (m - 2 * n >= 0) m -= 2 * n, ans += n;
    else ans += m / 2, m = 0;
    ans += m / 4;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int w,h,n;
  cin>>w>>h>>n;
  vector<vector<char>> grid(w,vector<char>(h,'W'));
  vector<tuple<int,int,int>> hoge(n);
  for(int i=0; i<n; i++){
    cin>>get<0>(hoge.at(i))>>get<1>(hoge.at(i))>>get<2>(hoge.at(i));
  }
  int minx=w,highx=0,miny=h,highy=0;
  for(int i=0; i<n; i++){
    int x,y,a;
    tie(x,y,a)=hoge.at(i);
    if(a==1&&highx<x){
      for(int i=0; i<x; i++){
        for(int j=0; j<h; j++){
          grid.at(i).at(j)='B';
        }
      }
      highx=x;
    }else if(a==2&&minx>x){
      for(int i=x; i<w; i++){
        for(int j=0; j<h; j++){
          grid.at(i).at(j)='B';
        }
      }
      minx=x;
    }else if(a==3&&highy<y){
      for(int i=0; i<w; i++){
        for(int j=0; j<y; j++){
          grid.at(i).at(j)='B';
        }
      }
      highy=y;
    }else if(a==4&&miny>y){
      for(int i=0; i<w; i++){
        for(int j=y; j<h; j++){
          grid.at(i).at(j)='B';
        }
      }
      miny=y;
    }
  }

int ans=0;
  for(int i=0; i<w; i++){
    for(int j=0; j<h; j++){
      if(grid.at(i).at(j)=='W'){
        ans++;
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>

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; }

constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1 << 28;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/
	int kkt = 89;
	while (kkt) {
		ll N; scanf("%lld", &N);
		int cnt = 0;
		while (N > 1) {
			cnt++;
		    int tmp = N%3>0;
			N /= 3;
			N+=tmp;
		}
		cout << cnt << endl;
		break;
	}

	return 0;

}


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

using namespace std;

int fr[31];

int main()
{
    int n , m , x , y;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        for(int j = 1 ; j <= x ; j++)
        {
            cin >> y;
            ++fr[y];
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= m ; i++)
        ans += (fr[i] == n);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)

int main(){
	int n,t[102],m,px[102][2],sum = 0;
	scanf("%d",&n);
	FOR(i,1,n+1){
		scanf("%d",&t[i]);
		sum += t[i];
	}
	scanf("%d",&m);
	FOR(i,0,m) scanf("%d %d",&px[i][0],&px[i][1]);

	FOR(i,0,m) printf("%d\n",sum - t[px[i][0]] + px[i][1]);
}

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

const int MAX_N = 1e5 + 5;
int N, T, A[MAX_N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> T;
    for(int i=0;i<N;i++) cin >> A[i];

    int mn = 1e9 + 1, mx = -1e9;
    map<int, int> cnt;
    for(int i=0;i<N;i++){
        mx = max(mx, A[i]-mn); cnt[A[i]-mn]++;
        mn = min(mn, A[i]);
    }

    cout << cnt[mx] << endl;
    return 0;
}


Measured memory_bytes: 5376
#include <iostream>
#include <vector>
#include <queue>

static const int L = (int)1e5;

int main() {
    std::vector<unsigned long long> lun(L);
    std::queue<unsigned long long> q({1, 2, 3, 4, 5, 6, 7, 8, 9});

    for (int l = 0; l < L; l++) {
        auto v = q.front(); q.pop();
        lun[l] = (v);

        auto d = v % 10;
        for (int i = -1; i < 2; i++) {
            auto dd = d + i;
            if (dd < 0 || 10 <= dd) {
                continue;
            }
            q.push(v * 10 + dd);
        }
    }

    int k; std::cin >> k;

    std::cout << lun[k-1]  << std::endl;
    return 0;
}

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

int main (void)
{
  char s[4];
  
  scanf("%s", s);
  
  if (!strcmp(s, "AAA") || !strcmp(s, "BBB")) {
    puts("No");
  } else {
    puts("Yes");
  }
  
  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int i = 0; i < n; i++){

			String mcxi1 = sc.next();
			String mcxi2 = sc.next();
			int val = 0;
			for(int j = 0; j < mcxi1.length(); j++){
				if(Character.isDigit(mcxi1.charAt(j))){
					val += Character.getNumericValue(mcxi1.charAt(j)) * reval(mcxi1.charAt(j + 1));
					j++;
				}else{
					val += reval(mcxi1.charAt(j));
				}
			}
			for(int j = 0; j < mcxi2.length(); j++){
				if(Character.isDigit(mcxi2.charAt(j))){
					val += Character.getNumericValue(mcxi2.charAt(j)) * reval(mcxi2.charAt(j + 1));
					j++;
				}else{
					val += reval(mcxi2.charAt(j));
				}
			}

			System.out.println(reviw(val));
		}
		
		
		sc.close();
	}
	static int reval(char x){
		if(x == 'm') return 1000;
		if(x == 'c') return 100;
		if(x == 'x') return 10;
		if(x == 'i') return 1;
		return -1;
	}
	static String reviw(int val){
		char[] c = {'m', 'c', 'x', 'i'};
		int[] x = {1000, 100, 10, 1};
		String res = "";
		for(int j = 0; j < c.length; j++){
			int tmp = val / x[j];
			if(tmp == 1){
				res = res + c[j];
			}else if(tmp > 1){
				res = res + tmp + c[j]; 
			}
			val = val % x[j];
		}
		return res;
	}
}

Measured memory_bytes: 39184
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		int ans = 1001;
		for(int i = 0; i < N; i++) {
			int c = sc.nextInt();
			int t = sc.nextInt();
			if(t <= T) {
				ans = Math.min(ans, c);
			}
		}
		if(ans <= 1000) {
			System.out.println(ans);
		} else {
			System.out.println("TLE");
		}
	}

}


Measured memory_bytes: 22740
#include<iostream>
using namespace std;
int main(){
 int H, W, h, w;
 while(1){
  cin >> H >> W;
  if( H == 0 && W == 0 )break;
  for( h = 0; h < H; h++){
   for( w = 0; w < W; w++){
    if( h == 0 || h == H-1 || w == 0 || w == W-1){
    cout << "#";
    }else{
    cout << ".";
    }
   }
  cout << "\n";
  }
 cout << endl;
 }
 return 0;
}

Measured memory_bytes: 3092
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
//#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M  1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000
#define N 100005
#define vi vector<int>
#define all(v) v.begin(),v.end()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int n,k;
   cin>>n>>k;
   vi a(n);
   rep(i,0,n)
   cin>>a[i];
   vi pre(n+1);
   for(int i=1;i<=n;i++)
   {
       pre[i]=pre[i-1]+a[i-1];
       pre[i]%=k;
   }
   for(int i=0;i<=n;i++)
   {
       pre[i]=(i - pre[i] + k)%k;
   }
   map<int,int>mp;
   int ans=0;
   int d=min(n+1,k);
   for(int i=0;i<d;i++)
   {
       ans+=mp[pre[i]];
       mp[pre[i]]++;
   }
   for(int i=d;i<=n;i++)
   {
       mp[pre[i - k]]--;
       ans+=mp[pre[i]]++;
   }
   cout<<ans<<endl;

}


Measured memory_bytes: 18696
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class A
{
	public static void Main()
	{
		int X = Int32.Parse(Console.ReadLine());
		int A = Int32.Parse(Console.ReadLine());
		int B = Int32.Parse(Console.ReadLine());
		Console.WriteLine((X-A) % B);
	}
}





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

namespace ArCorder
{
    class Program
    {
        static void Main()
        {

            int max = int.Parse(Console.ReadLine());
            string[] items = Console.ReadLine().Split(' ');
            if (items.Contains("Y"))
            {
                Console.WriteLine("Four");
            }
            else
            {
                Console.WriteLine("Three");
            }
 
        }
    }
}


Measured memory_bytes: 11220
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
struct edge{
	int s,t,nxt;
}e[200005];
int last[100005],e_cnt;
void ins(int a,int b){
	e[e_cnt]=(edge){a,b,last[a]};
	last[a]=e_cnt++;
}
int fa[100005],dep[100005];
void dfs(int x){
	for(int i=last[x];i!=-1;i=e[i].nxt)if(e[i].t!=fa[x]){
		fa[e[i].t]=x;
		dep[e[i].t]=dep[x]+1;
		dfs(e[i].t);
	}
}
vector<int> v;
int h[100005];
int p[100005],ans[100005];
int main(){
	int n;
	scanf("%d",&n);
	memset(last,-1,sizeof(last));
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		ins(u,v);
		ins(v,u);
		h[u]++;
		h[v]++;
	}
	dfs(1);
	int mx=1;
	for(int i=1;i<=n;i++)if(dep[i]>dep[mx])mx=i;
	fa[mx]=0;
	dep[mx]=0;
	dfs(mx);
	for(int i=1;i<=n;i++)if(dep[i]>dep[mx])mx=i;
	while(mx)v.push_back(mx),mx=fa[mx];
	int sz=v.size();
	for(int i=1;i<v.size()-1;i++){
		sz+=h[v[i]]-2;
	}
	if(sz<n){puts("-1"); return 0;}
	int l=v.size()-1;
	for(int i=1;i<v.size()-1;i++){
		if(h[v[i]]<h[v[l-i]])break;
		else if(h[v[i]]>h[v[l-i]]){reverse(v.begin(), v.end()); break;}
	}
	p[1]=1;
	for(int i=1,lst=2;i<v.size()-1;i++){
		p[lst]=lst+h[v[i]]-2;
		for(int j=lst;j<lst+h[v[i]]-2;j++)p[j+1]=j;
		lst+=h[v[i]]-2+1;
	}
	p[n]=n;
	for(int i=1;i<=n;i++)ans[p[i]]=i;
	for(int i=1;i<=n;i++)printf("%d ",ans[i]);
	return 0;
}

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

int main(void){
    int n, d;
    cin >> n >> d;
    int x[n][d], ans;
    int count = 0;

    rep(i, n)rep(j, d)
        cin >> x[i][j];

    rep(i, n){
        for(int j = i + 1; j < n; j++){
            ans = 0;

            rep(k, d){
                ans += pow(x[i][k] - x[j][k], 2);
            }
            if(floor(sqrt(ans)) == sqrt(ans))
                count++;
        }
    }
    cout << count << endl;
    return 0;
}


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


int main(){
    ll n;cin>>n;
    rep(i,0,n){
        ll a;cin>>a;
        if(a%2==0){
            if(a%3!=0&&a%5!=0){cout<<"DENIED"<<endl;return 0;}
    }
    }
    cout<<"APPROVED"<<endl;
}

    









Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void){
  int i;
  string n;
  cin >> n;
  for (i=1;i<n.size();i++) if (n[i]!='9') break;
  if (i==n.size()) cout << n[0]-'0'+9*(n.size()-1) << endl;
  else cout << n[0]-'0'-1+9*(n.size()-1) << endl;
  return 0;
}

Measured memory_bytes: 256
n,a,b = gets.split(' ').map(&:to_i)
#青と赤のボールを何回並べられるか回数を確認
num = n / (a+b)
#青と赤のボールを全部並べられないあまりはいくつか調べる。
extra = n % (a+b)
    
if a == 0
    puts 0
else
    if n <= a
        puts n
    else
        if extra == 0
            puts num * a
        else
            if extra > a
                puts (num * a) + a
            else
                puts (num * a) + extra
            end
        end
    end
end



Measured memory_bytes: 1788
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>

using sll = signed long long;
using ui = unsigned int;
using ull = unsigned long long;


auto power(ui base, ui exponent) {
	return
		static_cast<ull>
			(std::powl(base, exponent) );
}

int main() {
	sll n;
	std::cin >> n;


//	std::cout << -10 % 3 << "\n";
	std::string ans;
	ui i{};
	while (n != 0) {
		
		const auto rem = n % power(2, i + 1);

		ans += rem != 0 ? '1' : '0';
		n += rem * (i % 2 == 0 ? -1 : 1);

		++i;
	}

	if (ans.empty()) {
		std::cout << 0 << "\n";
	}
	else {
		for (ui i{}; i < ans.size(); ++i)
			std::cout << ans[ans.size() - i - 1];
		std::cout << "\n";
	}
}




Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    ans = 0
    pre = 1
    for _ in range(II()):
        a = II()
        if pre > a:
            continue
        if a % pre:
            ans += a // pre
            continue
        if pre == a:
            pre += 1
            continue
        tmp = a // pre - 1
        ans += tmp
        if pre == 1:
            pre += 1
    print(ans)

    return


#main
if __name__ == '__main__':
    solve()


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

int main(){
  string s,t;
  cin >> s >> t;
  for(int i = 0; i < s.size(); i++){
    s = s.substr(s.size()-1, 1) + s;
    s.pop_back();
    if(s == t){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int r, c;
    cin >> r >> c;
    int x[r][c+1];
    vector<int> column_sum(c+1);
    for(int i=0; i<r; i++){
        int r_i_sum = 0;
        for(int j=0; j<c; j++){
            int c_j;
            cin >> c_j;
            x[i][j] = c_j;
            r_i_sum += c_j;
        }
        x[i][c] = r_i_sum;
    }
    fill(column_sum.begin(), column_sum.end(), 0);
    for(int i=0; i<r; i++){
        for(int j=0; j<c+1; j++){
            column_sum[j] += x[i][j];
            cout << x[i][j];
            if(j != c) cout << " ";
        }
        cout << endl;
    }
    for(int j=0; j<c+1; j++){
        cout << column_sum[j];
        if(j != c) cout << " ";
    }
    cout << endl;
}


Measured memory_bytes: 3104
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int> PI;
#define MAX 99999999
vvi v(60,vi(60,0));
int w=12,h=12;
int mx[]={0,0,0,1,-1};
int my[]={1,0,-1,0,0};
void dfs(int y,int x){
    if (!v[y][x])return;
    if(v[y][x]){
        v[y][x]=0;
        rep(p,5){
            int tx=x+mx[p]; int ty=y+my[p];
            if(0<=tx&&tx<w&&0<=ty&&ty<h&&v[ty][tx]!=0){
                dfs(ty,tx);
            }
        }
    }
}
int main(){
    char hoge;
    while(cin>>hoge){
    v[0][0]=hoge-48;
    char s;
    rep(i,h)rep(j,w){
        if(!(i+j)) continue;
        cin>>s;
        v[i][j]=s-48;
    }
        int ans=0;
        rep(i,h)rep(j,w){
            if(v[i][j]){dfs(i,j);
                ans++;
            }
        }
        cout<<ans<<endl;
        rep(i,60)rep(j,60)v[i][j]=0;
    }
}

Measured memory_bytes: 3052
A, B, C, X, Y = map(int, input().split(" "))

a = 0
b = 0
c = 0

ABcand = min([X, Y])
if A + B >= C * 2:
    c += ABcand * 2
else:
    a += ABcand
    b += ABcand

if X == ABcand:
    res = Y - ABcand
    if B * res >= C * res * 2:
        c += res * 2
    else:
        b += res
else:
    res = X - ABcand
    if A * res >= C * res * 2:
        c += res * 2
    else:
        a += res
print(A*a+B*b+C*c)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#define int long long
int32_t main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int a,b,c,x, cnt = 0;
    cin>>a>>b>>c>>x;
    for(int i=0;i<=a;i++){
    	for(int j=0;j<=b;j++)
    		for(int k=0;k<=c;k++)
    			if(x == (i*500 + j*100 + k*50))
    				cnt++;
    }
    cout<<cnt;
}

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

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

int main() {
     // 入出力高速化
    cin.tie(0);
   	ios::sync_with_stdio(false);
    
    int a;
    string s;

    cin >> a;
    cin >> s;

    if (a >= 3200) {
        cout << s << '\n';
    } else {
        cout << "red\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

int main() {
	int n;
	cin >> n;
	int b[101];
	b[0] = b[n] = INF;
	rep1(i, n - 1) cin >> b[i];
	ll ans = 0;
	rep(i, n) ans += min(b[i], b[i + 1]);
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, _s, n) for(int i = _s, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
using namespace std;

#define repi(itr, ds) for(auto itr = ds.begin(); itr != ds.end(); itr++)
// vector
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for(T &x : vec) is >> x;
  return is;
}
// pair
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
// vector
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "{";
  for(int i = 0; i < vec.size(); i++) {
    os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
  }
  os << "}\n   ";
  return os;
}
// map
template <typename T, typename U>
ostream &operator<<(ostream &os, map<T, U> &map_var) {
  os << "{";
  repi(itr, map_var) {
    os << *itr;
    itr++;
    if(itr != map_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
// set
template <typename T>
ostream &operator<<(ostream &os, set<T> &set_var) {
  os << "{";
  repi(itr, set_var) {
    os << *itr;
    itr++;
    if(itr != set_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}

#define DUMPOUT cerr

void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&... tail) {
  DUMPOUT << head;
  if(sizeof...(Tail) > 0) {
    DUMPOUT << ", ";
  }
  dump_func(std::move(tail)...);
}
#ifdef DEBUG_
#define DEB
#define dump(...)                                                             \
  DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                             \
          << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \
          << "    ",                                                          \
      dump_func(__VA_ARGS__)
#else
#define DEB if(false)
#define dump(...)
#endif

typedef long long int ll;

int main() {
  int H, A;
  cin >> H >> A;
  int ans;
  if(H % A == 0) {
    ans = H / A;
  } else {
    ans = H / A + 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
class Imos_1:
    def __init__(self,N):
        self.len=N
        self.list=[0]*(N+1)

    def Add(self,F,T,C):
        self.list[F]+=C
        self.list[T+1]-=C

    def Cumulative_Sum(self):
        Y=[0]*(self.len)
        S=0
        for i in range(self.len):
            S+=self.list[i]
            Y[i]=S

        return Y

N,M=map(int,input().split())

I=Imos_1(N)
for _ in range(M):
    L,R=map(int,input().split())
    I.Add(L-1,R-1,1)

J=I.Cumulative_Sum()
print(J.count(M))


Measured memory_bytes: 79300
#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  
#include <numeric>
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define endl '\n'
using ll = long long;
 
const int precision = 3;
const int modulo =  1000000007; // 10^9 + 7
const ll lmodulo =  1000000007; // 10^9 + 7
 
const double EPS = 1e-9;
const ll inf = 1e18;

void solve () {
	int n, W;  cin >> n >> W;
	vector<int> weight(n), value(n);
	
	for (auto i = 0; i < n; ++i) {
		cin >> weight[i] >> value[i];
	}

	int maxVal = accumulate(value.begin(), value.end(), 0);

	vector<vector<ll>> dp(weight.size() + 1, vector<ll>(maxVal + 1, inf));
	dp[0][0] = 0;

	for (auto i = 1; i < dp.size(); ++i) {
		const auto & w = weight[i - 1];
		const auto & cv = value[i - 1];
		for (int v = maxVal; v >= 0; --v) {
			dp[i][v] = dp[i - 1][v];
			if (v - cv >= 0) {
				dp[i][v] = min(dp[i][v], dp[i - 1][v - cv] + w);
			}
		}
	}

	int ret = 0;
	for (int i = 0; i<= maxVal; ++i) {
		if(dp[n][i] <= W) {
			ret = max(ret, i);
		}
	}
	cout << ret;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.precision(precision);
  cout.setf(ios_base::fixed);
  solve();
  return 0;
}



Measured memory_bytes: 80256
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i = 0;i < n;i++)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()

template<class T> bool chmax(T& a,T b){ if(a < b){ a = b; return true; }else return false; }
template<class T> bool chmin(T& a,T b){ if(a > b){ a = b; return true; }else return false; }
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;
using vpi = vector<Pi>;
using vpl = vector<Pl>;
 
#define debug(arr) cout << #arr << " = " << arr << '\n'
#define debug2(a,b) cout << "[" << #a << "," << #b << "] = " << "[" << a << "," << b << "]" << '\n'
template<class T> ostream &operator << (ostream& out, const vector<T>& arr) {
	cout << "{"; for (int i = 0; i < arr.size(); i++)cout << (!i ? "" : ", ") << arr[i]; cout << "}";
	return out;
}
template<class T> ostream &operator << (ostream& out, const vector<vector<T> >& arr) {
	cout << "{\n"; for (auto& vec : arr)cout << "  " << vec << ",\n"; cout << "}";
	return out;
}
template<class S,class T> ostream &operator << (ostream& out, const pair<S,T>& p){
  cout << "{" << p.first << "," << p.second << "}" << '\n';
  return out;
}
template<class T> istream &operator >> (istream& in, vector<T>& arr) {
	for (auto& i : arr)cin >> i; return in;
}

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

int main(int argc, char const* argv[])
{
  int d,s,t;cin >> d >> s >> t;
  if (s * t >= d) {
    cout << "Yes" << '\n';
  }else{
    cout << "No" << '\n';
  }
  return 0;
}


Measured memory_bytes: 3600
program making_palindrome
  implicit none
  integer(8), parameter :: inf = 1e18
  integer :: n, i
  character(20) :: s(50, 2) = ''
  integer(8) :: c(50) = 0, m(50, 21, 2) = 0, x = inf
  logical :: u(50, 21, 2) = .false.
  read(*,*) n
  do i = 1, n
    read(*,*) s(i, 1), c(i)
    s(i, 2) = reverse(s(i, 1)(1:len_trim(s(i, 1))))
  end do
  do i = 1, n
    x = min(x, solve(i, 1, 1) + c(i))
  end do
  write(*,'(i0)') merge(x, -1_8, x < inf)
contains
  function reverse(s) result(res)
    character(*), intent(in) :: s
    character(len_trim(s)) :: res
    integer :: n, i
    n = len_trim(s)
    do i = 1, n
      res(i:i) = s(n - i + 1:n - i + 1)
    end do
  end
  recursive integer(8) function solve(i, j, k) result(res)
    integer, intent(in) :: i, j, k
    integer :: l, r, t
    logical :: f
    res = m(i, j, k)
    if (u(i, j, k)) return
    u(i, j, k) = .true.
    m(i, j, k) = inf
    l = j
    r = len_trim(s(i, k))
    f = .true.
    do while (l < r)
      if (s(i, k)(l:l) /= s(i, k)(r:r)) then
        f = .false.
        exit
      end if
      l = l + 1
      r = r - 1
    end do
    if (f) then
      m(i, j, k) = 0
      res = 0
      return
    end if
    do t = 1, n
      l = j
      r = 1
      do while (l <= len_trim(s(i, k)) .and. r <= len_trim(s(t, 3 - k)))
        if (s(i, k)(l:l) /= s(t, 3 - k)(r:r)) exit
        l = l + 1
        r = r + 1
      end do
      if (l == len_trim(s(i, k)) + 1) then
        m(i, j, k) = min(m(i, j, k), solve(t, r, 3 - k) + c(t))
      end if
      if (r == len_trim(s(t, 3 - k)) + 1) then
        m(i, j, k) = min(m(i, j, k), solve(i, l, k) + c(t))
      end if
    end do
    res = m(i, j, k)
  end
end program making_palindrome

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
template<class T>bool chmin(T&a,const T&b){return a>b?(a=b,true):false;}
template<class T>bool chmax(T&a,const T&b){return a<b?(a=b,true):false;}

int nextInt() { int x; scanf("%d", &x); return x;}

int main2() {
  int X = nextInt();
  int Y = nextInt();
  int Z = nextInt();
  vector<string> v;
  REP(i, X) v.push_back("a");
  REP(i, Y) v.push_back("b");
  REP(i, Z) v.push_back("c");
  while (v.size() > 1) {
    sort(v.begin(), v.end());
    v.front() += v.back();
    v.erase(v.begin() + v.size() - 1);
  }
  cout << v.front() << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}



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

using ll = long long int;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

#define pi 3.14159265358979

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


bool my_cp(pair<int, int> a, pair<int, int> b){
  return (double)b.first / (double)(b.second+1) < (double)a.first / (double)(a.second+1);
}


ll cnt_rep = 0;
ll powmod(ll N, ll P, ll M){
  cnt_rep++;
  if(P == 0) return 1;
  if(P%2 == 0){
    ll t = powmod(N, P/2, M);
    return t*t % M;
  }
  return (N * powmod(N, P-1, M)) % M;
}

int N;

void dfs(string s, char m, int N){
  size_t len = s.length();
  if(len == N){
    cout << s << endl;
  }else{
    for(char c = 'a'; c <= m; c++){
      dfs(s + c, ((c == m)? (m + 1) : m), N);
    }
  }
}


ll gcd(ll a, ll b){
  ll resi, g, l;
  if(a > b){
    g = a; l = b;
  }else if(b > a){
    g = b; l = a;
  }else{
    return a;
  }
  resi = g % l;
  if(resi != 0){
    return gcd(l, resi);
  }else{
    return l;
  } 
}





// substr(start, len)

int main(){

  string s;
  cin >> s;

  vector<ll> m(2019, 0);
  m[0]++;

  ll a = 0, digit = 0;

  // 左から桁を増やし，それぞれのmodを求める
  for(ll i = s.length()-1; i >= 0; i--){
    a += (s[i] - '0') * powmod(10, digit, 2019);
    a %= 2019;
    m[a]++;
    digit++;
  }

  ll ans = 0;

  rep(i, 0, 2019){
    ans += m[i]*(m[i]-1) / 2;
  }

  cout << ans << endl;


  
  // cout << setprecision(8) << ans << endl;  // For double
  // CHECK if it's possible to overflow!!
}

Measured memory_bytes: 3696
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    int n, k;
    cin >> n >> k;
    ll s;
    cin >> s;
    rep(i, k) {
        if ( i >= 1 ) cout << " ";
        cout << s;
    }
    rep(i, n - k) {
        cout << " ";
        if ( s == 1e9 ) cout << 1;
        else            cout << s + 1;
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 1280
#include <iostream>

using namespace std;

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

    bool flg = false;
    for (int i = 0; i< s.length(); i++) {
        if (s[0] == t[i]) {
            flg = true;
            for (int j = 1; j< s.length(); j++) {
                if (s[(0 + j) % s.length()] != t[(i + j) % s.length()]) {
                    flg = false;
                }
            }
            if (flg) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;

    return 0;
}


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

const int MAX_N = 1e5 + 10;
const int MAX_M = (MAX_N << 1) - 1;
const int LSIZE = (MAX_M + 7) >> 3;

pii table[15][LSIZE];
pii mini[9][1 << 7];
int buck[LSIZE];
int off[LSIZE];


int it = 0;

int vs[MAX_M];
int id[MAX_N];

int n;
vector<int> G[MAX_N];

void dfs(int v) {
	id[v] = it;
	if (it) {
		buck[(it - 1) >> 3] |= 1 << ((it - 1) & 7);
	}
	vs[it++] = v;
	for (auto to : G[v]) {
		dfs(to);
		vs[it++] = v;
	}
}

void bitDP() {
	mini[0][0] = { 1e9, -100 };
	for (int b = 0; b < 8; b++) {
		for (int i = 0; i < (1 << b); i++) {
			int mi = 0, id = 0, t = 0;
			for (int j = 0; j < b; j++) {
				t += (((i >> j) & 1) << 1) - 1;
				if (t < mi) {
					mi = t;
					id = j + 1;
				}
			}
			mini[b + 1][i] = { mi, id };
		}
	}
}

void init() {
	bitDP();
	int m = (n << 1) - 1;
	int l = (m + 7) >> 3;
	dfs(0);
	off[0] = 0;
	for (int i = 0; i < l; i++) {
		pii tmp = mini[min(m - (i << 3), 8)][buck[i] & ((1 << 7) - 1)];
		table[0][i] = { tmp.first + off[i], tmp.second + (i << 3) };
		off[i + 1] = off[i] + (__builtin_popcount(buck[i]) << 1) - 8;
	}
	int h = 31 - __builtin_clz(l);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j + (1 << i) < l; j++) {
			table[i + 1][j] = min(table[i][j], table[i][j + (1 << i)]);
		}
	}
}

pii get_buck(int l, int r) {
	pii tmp = mini[r - l][(buck[l >> 3] & ((1 << ((r - 1) & 7)) - 1)) >> (l & 7)];
	return pii(off[l >> 3] + (__builtin_popcount(buck[l >> 3] & ((1 << (l & 7)) - 1)) << 1) - (l & 7) + tmp.first, l + tmp.second);
}

int lca(int u, int v) {
	u = id[u], v = id[v];
	if (u > v) swap(u, v);
	v++;
	if (((u + 7) >> 3) > (v >> 3)) {
		return vs[u + mini[v - u][(buck[u >> 3] & ((1 << ((v - 1) & 7)) - 1)) >> (u & 7)].second];
	}
	pii left = get_buck(u, (u + 7) & (~7));
	pii right = get_buck(v & (~7), v);
	u = (u + 7) >> 3;
	v >>= 3;
	if (u == v) {
		return vs[min(left, right).second];
	}
	int b = 31 - __builtin_clz(v - u);
	return vs[min(min(left, right), min(table[b][u], table[b][v - (1 << b)])).second];
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int c;
			cin >> c;
			G[i].push_back(c);
		}
	}
	init();
	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		printf("%d\n", lca(u, v));
	}
	return 0;
}



Measured memory_bytes: 15928
#include <stdio.h>
#include <string.h>
#define rep(i,l,n) for(i=l;i<n;i++)

int main(void){
	char s[101];
	char p[101];
	int i,j,ls,lp,a,m;
	
	scanf("%s",s);
	scanf("%s",p);
	
	ls=strlen(s);
	lp=strlen(p);
	
	a=0;
	
	rep(i,0,ls){
		if(a) break;
		rep(j,0,lp){
			m=i+j;
			if(m>=ls) m-=ls;
			if(s[m]!=p[j]) break;
			if(j==lp-1) a++;
			
		}
	}
	
	if(a) printf("Yes\n");
	else printf("No\n");
	
	return 0;
}


Measured memory_bytes: 2096
import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
val =[0]*(cap+1)
def nap(n,cap):
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap,w-1,-1):
            nv=val[wk-w]+v
            if val[wk]<nv:
                val[wk]=nv
    return max(val)
print(nap(n,cap))


Measured memory_bytes: 9460
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

lint dp[101][100001];
lint w[100],v[100];
lint N,W;

lint calc(lint i,lint j){
    if(dp[i][j]>=0) return dp[i][j];
    lint res;
    if(i==N) res=0;
    else if(j<w[i]) res=calc(i+1,j);
    else res=max(calc(i+1,j),calc(i+1,j-w[i])+v[i]);
    return dp[i][j]=res;
}

int main(void){
    cin >> N >> W;
    rep(i,N) cin >> w[i] >> v[i];
    rep(i,101) rep(j,100001) dp[i][j]=-1;
    cout << calc(0,W) << endl;
}

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

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

int main(){
    int n;
    cin >> n;
    map<int,int> mp;
    ll sum=0;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        mp[x]++;
        sum+=x;
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int b,c;
        cin >> b >> c;
        if(mp[b]==0) cout << sum << endl;
        else{
            sum-=(ll)b*mp[b];
            sum+=(ll)c*mp[b];
            mp[c]+=mp[b];
            mp[b]=0;
            cout << sum << endl;
        }
    }
}

Measured memory_bytes: 7736
#include<iostream>
using namespace std;
bool flag1[1005],flag2[1005];
char ch[1005][1005];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>ch[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(ch[i][j]=='#')
			{
				flag1[i]=1;
				break;
			}
		}
	}
	for(int j=1;j<=m;j++)
	{
		for(int i=1;i<=n;i++)
		{
			if(ch[i][j]=='#')
			{
				flag2[j]=1;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!flag1[i]) continue;
		for(int j=1;j<=m;j++)
		{
			if(!flag2[j]) continue;
			cout<<ch[i][j];
		}
		cout<<endl;
	}
	return 0;
}

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

const ll INF = 1LL << 60;


// const int mod = 1000000007;
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};


int main() {
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    long long K;
    scanf("%lld",&K);

    combination comb = combination(200010);

    mint ans = 0;
    mint color = M;

    // くっつける点
    for (int x = N - 1; x >= 0; x--) {
      mint tmp = color;
      tmp *= comb(N - 1, x);

      if (x <= K) ans += tmp;
      color *= (M - 1);
    }
    cout << ans << endl;
}


Measured memory_bytes: 6408
N,K = map(int,input().split())
R,S,P = map(int,input().split())
score_dic = {"r":R,"s":S,"p":P}
win_dic = {"r":"p","s":"r","p":"s"}
T = list(input())
score = 0
for i in range(0,N,1):
    if i >= K and T[i-K] == T[i]:
        T[i]="m"
    else:
        score+=score_dic[win_dic[T[i]]]

print(score)

Measured memory_bytes: 49552
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
const int INF = 1e18;

signed main(){
    int a, v, b, w ,t ; cin >> a >> v >> b >> w >> t;
    int dist = abs(a-b);
    if(w>=v){
        cout << "NO" << endl;
        return 0;
    }
    cout << (dist <= t*(v-w) ? "YES" : "NO") << endl;
}

Measured memory_bytes: 3624
h,w=map(int,input().split())
s=eval('input(),'*h)
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':continue
        for y,x in((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
            if h>y>=0 and w>x>=0 and s[y][x]=='#':
                break
        else:
            print('No')
            exit()
print('Yes')

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

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

  vector<pair<int, int> > v;
  vector<int> u[100001];
  for(int i = 0; i < m; i++){
    int p, y;
    cin >> p >> y;
    v.push_back(make_pair(p, y));
    u[p].push_back(y);
  }

  for(int i = 1; i <= n; i++){
    sort(u[i].begin(), u[i].end());
  }

  for(int i = 0; i < m; i++){
    int p = v[i].first;
    printf("%06d%06d\n", p, (int)(lower_bound(u[p].begin(), u[p].end(), v[i].second) - u[p].begin() + 1));
  }

  return 0;
}


Measured memory_bytes: 7796
<?php
$input1 = fgets(STDIN);
// $input1 = '100 3';
$temps = explode(' ',$input1);
$h = intval($temps[0]);
$n = intval($temps[1]);

$input2 = fgets(STDIN);
// $input2 = '10 100 2';
$temps = explode(' ',$input2);

for($i=0;$i<$n;$i++){
    $h -= intval($temps[$i]);
}

if($h > 0){
    echo 'No';
}else{
    echo 'Yes';
}

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

using namespace std;

int gcd(int a, int b) {
	if (b == 0)
		return a;
	if (a < b) {
		int buf = a;
		a = b;
		b = buf;
	}
	return gcd(b, a % b);
}

int main(void) {
	int num, st, i = 0, ans;
	cin >> num >> st;
	vector<int> d(num);
	for (; i < num; i++) {
		scanf("%d", &d[i]);
		d[i] = abs(d[i] - st);
	}
	for (ans = d[0], i = 1; i < num; i++)
		ans = gcd(ans, d[i]);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include <algorithm>
#include <stdlib.h>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <iomanip>
#include <queue>

#define PI 3.14159265358979
#define MOD 1000000007

//fixed << setprecision(15) <<

using namespace std;

int main(void) {
	long long int x,y,l, m, n,num,sum;
	priority_queue <long long int, vector<long long int>, less<long long int>>a, b, c;
	priority_queue <long long int, vector<long long int>, greater<long long int>>d;
	int i, j, k;
	cin >> x >> y >> l >> m >> n;
	for (i = 0; i < l; i++) {
		cin >> num;
		a.push(num);
	}
	for (i = 0; i < m; i++) {
		cin >> num;
		b.push(num);
	}
	for (i = 0; i < n; i++) {
		cin >> num;
		c.push(num);
	}
	for (i = 0; i < x; i++) {
		d.push(a.top());
		a.pop();
	}
	for (i = 0; i < y; i++) {
		d.push(b.top());
		b.pop();
	}
	while (c.empty() == false) {
		if (d.top() < c.top()) {
			d.push(c.top());
			d.pop();
			c.pop();
		}
		else break;
	}
	sum = 0;
	for (i = 0; i < x + y; i++) {
		sum += d.top();
		d.pop();
	}
	cout << sum << endl;
	return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define INF (int)1e9
#define MINF -(int)1e9
#define EPS 1e-9
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.1415926535
#define ff first
#define ss second

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {
	out << "[" << par.first << ";" << par.second << "]";
	return out;
}

template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) {
	out << "{";
	for( const auto &x:cont) out << x << ", ";
	out << "}";
	return out;
}

template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {
	out << "{";
	for( const auto &x:cont) out << x << ", ";
	out << "}";
	return out;
}

template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){
    out << "[";
    REP(i, v.size()) out << v[i] << ", ";
    out << "]";
    return out;
}
        

int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    vi arr(n);
    REP(i, n) cin >> arr[i];
    vi cnt1(1e5+5,0);
    vi cnt2(1e5+5, 0);
    REP(i, n){
        if(i%2 == 0) cnt1[arr[i]]++;
        else cnt2[arr[i]]++;
    }
    vector<pii> xx;
    vector<pii> xx2;
    REP(i, (int)1e5 + 5){
        xx.pb(mp(cnt1[i], i));
        xx2.pb(mp(cnt2[i],i));
    }
    sort(xx.begin(), xx.end(), greater<pii>());
    sort(xx2.begin(), xx2.end(), greater<pii>());
    int ans = INF;
    if(xx[0].ss != xx2[0].ss) ans = min(ans, n - xx[0].ff - xx2[0].ff);
    else{
        ans = min(ans, n - xx[1].ff - xx2[0].ff);
        ans = min(ans, n - xx[0].ff - xx2[1].ff);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6320
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = INT_MAX;
const int MOD = 1000000007;
const long long INF = LLONG_MAX;

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

int x, y;

int main() {
  cin >> x >> y;
  if (x == 2) {
    if (y == 2) {
      cout << "Yes";
    } else {
      cout << "No";
    }
  } else if (x == 4 || x == 6 || x == 9 || x == 11) {
    if (y == 4 || y == 6 || y == 9 || y == 11) {
      cout << "Yes";
    } else {
      cout << "No";
    }
  } else {
    if (y == 1 || y == 3 || y == 5 || y == 7 || y == 8 || y == 10 || y == 12) {
      cout << "Yes";
    } else {
      cout << "No";
    }
  }
}


Measured memory_bytes: 3636