akhauriyash/Code-Regression huggingface dataset:
let rec gcd a b = if b = 0 then a else gcd b (a mod b)
let () =
  Scanf.scanf "%d %d %d %d" @@ fun a b c d ->
  let f x = b / x - (a-1) / x in
  b - a + 1 - f c - f d + f (c / gcd c d * d)
  |> Printf.printf "%d\n"


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define pb push_back
#define all(a) a.begin(),a.end()
#define i64 long long int
const double pi = 2*acos(0) ;
const int maxn = (i64)2e5+5;

int main()
{
    int n,k,q,i,a;
    cin>>n>>k>>q;
    int arr[n+2] = {0};
    for(i = 0 ; i<q ; i++)
    {
        cin>>a;
        arr[a]++;
    }
    for(i = 1 ; i<=n ; i++)
    {
        if(((arr[i]+k)-q)>0) pf("Yes\n");
        else pf("No\n");
    }
return 0;
}


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

l = [[int(i) for i in input().split(" ")] for _ in range(1, n)]


for i in range(n-1):
  t = 0
  t += l[i][1] + l[i][0]
  for j in range(i+1, n-1):
    if t <= l[j][1]:
      t = l[j][1] + l[j][0]
    elif t % l[j][2] == 0:
      t += l[j][0]
    else:
      t += l[j][2] - (t % l[j][2]) + l[j][0]
  print(t)
    
print(0)

Measured memory_bytes: 3188
/**akshaykumar99**/
 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using id_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> ;
template<typename T> using id_setp = tree<pair<T,T>,null_type,less<pair<T,T>>,rb_tree_tag,tree_order_statistics_node_update> ;
 
#define f(i,x,n) for(i=x;i<n;i++)
#define fr(i,x,n) for(i=x;i>=n;i--)
#define pu push_back           
#define pp pop_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SP(x) fixed<<setprecision(x)
#define IOS() ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
const long long MOD=1e9+7;
const long double PI = acos(-1);
const long long INF=INT_MAX;
const long long LINF=LLONG_MAX;
const long long N=2e5+1;
 
typedef long long ll;
typedef long double ld;

int main()
{
    IOS();
    
   	ll n[2],m,i,j;
   	cin>>n[0]>>n[1];
   	sort(n,n+2);
   	if(n[0]!=n[1])
   	f(i,0,n[1])
   	{
   		cout<<n[0];
   	}
   	else
   		f(i,0,n[1])
   			cout<<n[1];
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
const ll INF=1e9+7;
const ll N = 200003;
ll n,m,a,b;
ll go[N];

int main(){
	FOR(i,0,N)go[i]=0;
	cin>>n>>m;
	bool ans=false;
	FOR(i,0,m){
		cin>>a>>b;
		if(a==1||b==n){
			ll k=a;
			if(a==1)k=b;
			go[k]++;
			if(go[k]==2)ans=true;
		}
	}
	if(ans){
		cout<<"POSSIBLE"<<endl;
	}else{
		cout<<"IMPOSSIBLE"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#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()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------

void _main() {
	int N;
	cin >> N;
	int arrayV[50];
	for (int i = 0; i < N; i++) {
		cin >> arrayV[i];
	}
	int answer = 0;
	int arrayC[50];
	for (int j = 0; j < N; j++) {
		cin >> arrayC[j];
		if (arrayV[j] > arrayC[j]) {
			answer += arrayV[j] - arrayC[j];
		}
	}
	cout << answer << endl;
}

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

int main(){
	int num[5];
	int m1 = -2147483647, m2 = -2147483647, m3 = -2147483647, m4 = -2147483647, m5 = -2147483647;
        int p1 = 0, p2 = 0, p3 = 0, p4 = 0;
	cin >> num[0] >> num[1] >> num[2] >> num[3] >> num[4];

	for(int i=0; i<5; i++){
		if(m1 < num[i]){
                      m1 = num[i];
                      p1 = i;
                }
	}

	for(int i=0; i<5; i++){
   		if(i == p1) continue;
		else if(m2 < num[i]){
			m2 = num[i];
			p2 = i;
		}	
	}
	for(int i=0; i<5; i++){
   		if(i == p2 || i == p1) continue;
		else if(m3 < num[i]){
			m3 = num[i];
			p3 = i;
		}
	}
	for(int i=0; i<5; i++){
   		if(i == p3 || i == p1 || i == p2) continue;
		else if(m4 < num[i]){
			m4 = num[i];
			p4 = i;
		}	
	}
	for(int i=0; i<5; i++){
   		if(i == p4 || i == p1 || i == p2 || i == p3) continue;
		else if(m5 < num[i]){
			m5 = num[i];
		}	
	}
	cout << m1 << " " << m2 << " " << m3 << " " << m4 << " " << m5 << endl;

	return 0;

}

Measured memory_bytes: 1164
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    int x,y,z;
    char token[300]={};
    fgets(token, sizeof(token), stdin);
    x=atoi(strtok(token, " "));y=atoi(strtok(NULL, " "));z=atoi(strtok(NULL, " "));
    printf("%d %d %d",z,x,y);
    return 0;
}




Measured memory_bytes: 256
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[11001];
int main() {
	int N, W;//Nは品物の数　Wは荷物の重さの上限
	cin >> N >> W;
	vector<int>vs(N);
	vector<int>ws(N);
	for (int i = 0; i < N; i++) {
		cin >> vs[i] >> ws[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = W; j >= 0; j--) {
			dp[j + ws[i]] = max(dp[j + ws[i]], dp[j] + vs[i]);
		}
	}
	cout << dp[W] << endl;
	return 0;
}


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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x...) cerr << "[" << #x << "]: " << x << "\n";

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pl;

ld const PI = 4*atan((ld)1);

ll const mod = 1e9 + 7;

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

ll sub(ll a, ll b)
{
	return (a - b + mod) % mod;
}

ll mul(ll a, ll b)
{
	return (a * b) % mod;
}

ll fpow(ll x, ll y)
{
	ll res = 1;
	while (y)
	{
		if (y & 1) res = mul(res, x);
		x = mul(x, x);
		y /= 2;
	}
	return res;
}

int main()
{
	fastio;

	int n;
	cin >> n;

	if (n == 1)
	{
		cout << 0 << '\n';
	}
	else
	{
		ll a = fpow(10, n);
		ll b = fpow(9, n);
		ll c = fpow(8, n);

		a = sub(a, b);
		a = sub(a, b);
		a = add(a, c);
		cout <<a << '\n';
	}

	return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    string s;
    cin >> s;
    int l = 0, r = s.size() - 1;
    int res = 0;
    while (l < r) {
        if (s[l] == s[r]) {
            ++l;
            --r;
        } else if (s[l] == 'x') {
            ++l;
            ++res;
        } else if (s[r] == 'x') {
            --r;
            ++res;
        } else {
            res = -1;
            break;
        }
    }
    cout << res << endl;

    return 0;
}


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

int isprime(int x){
  if( x == 2) return 1;
  if( x < 2 || x % 2 == 0 ) return 0;
  
  int i = 3;
  while( i <=  sqrt(x) ){
    if( x % i == 0) return 0;
    i = i + 2;
  }
  return 1;
}

int main(){
  int n, a, i, sum = 0;
  cin >> n;
  for( i = 0; i < n; i++){
    cin >> a;
    sum += isprime(a);
  }
  cout << sum << endl;
}


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <string>
#include <stack>
#include <regex>
#include <numeric>
#include <queue>
#include <set>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

ll n, k;
vector<vector<ll>> v;

void solv(ll cnt)
{
  for (ll i = 1; i <= n - 2; i++)
  {
    for (ll j = i + 1; j <= n - 1; j++)
    {
      if (cnt == 0)
        return;
      v[i].push_back(j);
      cnt--;
    }
  }
}

int main(int argc, char const *argv[])
{
  cin >> n >> k;
  v = vector<vector<ll>>(n, vector<ll>());
  if (((n - 2) * (n - 1)) / 2 >= k)
  {
    REP(i, n - 1)
    {
      v[0].push_back(i + 1);
    }
    ll cnt = ((n - 2) * (n - 1)) / 2 - k;
    solv(cnt);
    cout << n - 1 + cnt << endl;
    for (auto i = v.begin(); i < v.end(); i++)
    {
      for (auto j : *i)
      {
        cout << i - v.begin() + 1 << " " << j + 1 << endl;
      }
    }
  }
  else
  {
    cout << -1 << endl;
  }
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>

#define LL long long

using namespace std;

int main()
{
	while (1) {
		int n; cin >> n;
		if (n == 0) { break; }
		vector <int> vec(n);
		int sum = 0, ans = 0;
		for (int i = 0; i < n; i++) {
			int j; cin >> j;
			vec[i] = j;
			sum += j;
		}
		double avr = sum / n;
		for (int i = 0; i < n; i++) {
			if (vec[i] <= avr) { ans++; }
		}
		cout << ans << endl;
	}
	return 0;
}


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

int main(){
	string in;
	while( cin >> in ){
		int joiCnt=0, ioiCnt=0;
		for( int i=0; i<in.length()-2; i++ ){
			string buf = in.substr(i, 3);
			if( buf == "JOI" )		joiCnt++;
			else if( buf == "IOI" )	ioiCnt++;
		}
		cout << joiCnt << endl;
		cout << ioiCnt << endl;
	}
	return 0;
}

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

int main() {
	int K, S;
	scanf("%d%d", &K, &S);
	int ans = 0;
	for(int i = 0, n = min(S, K); i <= n; i++) {
		int rem = S - i;
		if(rem <= K) ans += rem + 1;
		else if(rem <= 2 * K) ans += 2 * K - rem + 1;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 256
i = 0
j = 0

k = 0
l = 0
m = 0

n = 0
a = []
num = []
count = 0
check = []

while True:
    a.append(list(map(int, input().split())))
    if a[n][0] == 0 and a[n][1] == 0:
        break
    n += 1

while i < n:
    count = 0
    check.append(0)
    num = []
    j = 0
    while True:
        count += 1
        num.append(count)
        if count == a[i][0]:
            break
    
    for j in range(len(num)):
        if j + 2 > len(num):
            break

        for k in range(j + 1, len(num)):

            for l in range(k + 1, len(num)):
                if num[j] + num[k] + num[l] == a[i][1]:
                    check[i] += 1
    i += 1

i = 0
while i < n:
    print("%s" % check[i])
    i += 1

            
        

        




Measured memory_bytes: 5608
# Panasonic2020 D - String Equivalence
def generator(n):
    if n == 1:
        yield [0]
    else:
        for A in generator(n - 1):
            for i in range(max(A) + 2):
                A.append(i)
                yield A
                A.pop()


n = int(input())
for A in generator(n):
    s = ''
    for a in A:
        s += chr(a + 97)
    print(s)


Measured memory_bytes: 4412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
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; }
int main(){
    string s; cin>>s;
    ll n=s.size()+1;
    ll leq=0, geq=0, res=0;
    rep(i,n-1){
        if(geq==0 && s[i]=='<') leq++;
        else if(s[i]=='>') geq++;
        else{
            for(ll i=1; i<=max(leq, geq); i++) res+=i;
            for(ll i=1; i<min(leq, geq); i++) res+=i;
            geq=0; leq=1;
        }
    }
    for(ll i=1; i<=max(leq, geq); i++) res+=i;
    for(ll i=1; i<min(leq, geq); i++) res+=i;
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //long longをllで表せる
 
int main() {
  string a;
  string b;
  cin>>a>>b;
  int count=0;
  
  for (int i = 0; i < a.size(); i++) {
    if(a.at(i)!=b.at(i)){count++;}
}
  
  if(count==0){cout<<"Yes";}
  else{cout<<"No";}
}

Measured memory_bytes: 3636
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <string>
#include <iostream>
#include <stack>
#include <tuple>
#include <map>
#include <cassert>

using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    // b, a
    vector<pair<ll, ll>> tasks;
    for(ll i = 0; i < n; ++i){
        ll a, b;
        cin >> a >> b;
        tasks.push_back(make_pair(b, a));
    }
    sort(tasks.begin(), tasks.end());
    ll t = 0;
    for(ll i = 0; i < tasks.size(); ++i){
        t += tasks.at(i).second;
        if(t > tasks.at(i).first){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 6256
def mul(x, y)
  if x == '2' && y == '2' then '2'
  elsif x == '0' || y == '0' then '0'
  else '1'
  end
end

def plus(x, y)
  if x == '0' && y == '0' then '0'
  elsif x == '2' || y == '2' then '2'
  else '1'
  end
end

def to_num(s)
  ['0', '1', '2'].repeated_permutation(3).map { |p, q, r|
    s.gsub(/P|Q|R/, 'P' => p, 'Q' => q, 'R' => r)
  }
end

def calc(expr)
  while expr.size > 1
    expr.gsub!(/-(\d)/) {
      x = $1
      (2 - x.to_i).to_s
    }
    expr.gsub!(/\((\d)\+(\d)\)/) {
      x, y = $1, $2
      plus($1, $2)
    }
    expr.gsub!(/\((\d)\*(\d)\)/) {
      x, y = $1, $2
      mul($1, $2)
    }
  end
  if expr == '2' then return true
  else return false
  end
end

while s = gets.chomp
  break if s == "."
  puts to_num(s).count{ |expr| calc(expr) }
end

Measured memory_bytes: 9692
#!/usr/bin/env python
import os
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from io import BytesIO, IOBase
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (
    acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians,
    sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


def inlist():
    return(list(map(int, input().split())))


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))


def main():
    s = input()
    if "RRR" in s:
        print(3)
    elif "RR" in s:
        print(2)
    elif "R" in s:
        print(1)
    else:
        print(0)


if __name__ == "__main__":
    main()


Measured memory_bytes: 10536
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define tll tuple<ll, ll, ll>
#define all(c) c.begin(),c.end()

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
 
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;

char albt[26] = {'a','b','c','d','e','f','g','h','i','j','k','l',
                 'm','n','o','p','q','r','s','t','u','v','w','x',
                 'y','z'};

//vector<ll> g[202020];
//fill(score, score+202020, 0);
//vector<ll> v;

int main(){
  ll A, B;
  cin >> A >> B;
  ll size = 100;
  
  char G[size][size];
  for (int i=0;i<size;i++){
    for (int j=0;j<size;j++){
      if (i < size/2) G[i][j] = '#';
      else if (i >= size/2) G[i][j] = '.';
    }
  }
  
  ll wx = 0;
  ll wy = 0;
  for (int i=1;i<A;i++){
    G[wy][wx] = '.';
    wx += 2;
    if (wx >= size){
      wx = 0;
      wy += 2;
    }
  }
  
  ll bx = 0;
  ll by = size/2 + 1;
  for (int i=1;i<B;i++){
    G[by][bx] = '#';
    bx += 2;
    if (bx >= size){
      bx = 0;
      by += 2;
    }
  }
  
  cout << size << " " << size << endl;
  for (int i=0;i<size;i++){
    for (int j=0;j<size;j++){
      cout << G[i][j];
    }
    cout << endl;
  }
  //cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <fstream>
#define ni(n) scanf("%d", &n)
#define nl(n) scanf("%I64d", &n)
#define nai(a,n) for (int i = 0; i < (n); i++) ni((a)[i])
#define nal(a,n) for (int i = 0; i < (n); i++) nl((a)[i])
#define case(t) printf("Case #%d: ", (t))
#define pii pair<int, int>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
using namespace std;

int len(int x)
{
    int r = 0;
    while (x > 0) x /= 10, r++;
    return r;
}

int main()
{
    int a, b;
    ni(a), ni(b);
    int l = len(b);
    for (int i = 0; i < l; i++) a *= 10;
    a += b;
    for (int i = 0; i < 1000; i++) if (i * i== a)
    {
        printf("Yes\n");
        return 0;
    }
    printf("No\n");
    return 0;
}


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

int main(int argc, char **argv) {
  int i;
  int N, A, B;
  int sumA, sumB;
  cin >> N >> A >> B;
  sumA = N * A;
  sumB = B;

  if (sumA < sumB)
    cout << sumA << endl;
  else
    cout << sumB << endl;

  return 0;
}


Measured memory_bytes: 256
#pragma region RegionDefs
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,l,r) for(int i=(l),i##_len=(r);i<i##_len;++i)
#define all(x) begin(x),end(x)
using namespace std;
const int INF = 1e9;
template<class T=int> using V = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
//const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
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 (a>b) {a=b; return 1;} return 0;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#define YN(e) cout << ((e) ? "YES" : "NO") << endl
#define yn(e) cout << ((e) ? "Yes" : "No") << endl
#pragma endregion RegionDefs

const int MAX = 510000;
const int MOD = 998244353;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

void solve()
{
    COMinit();
    IN(n, m, k);
    ll ans = 0;
    rep(i, k+1)
    {
        ans = (ans + (COM(n-1, i) * m) % MOD * modpow(m-1, n-i-1, MOD) % MOD) % MOD;
    }
    cout << ans << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

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

int main(){
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int dx = x2 - x1;
    int dy = y2 - y1;
    int x3 = x2 - dy;
    int y3 = y2 + dx;
    int x4 = x3 - dx;
    int y4 = y3 - dy;
    cout << x3 << ' ' << y3 << ' ' << x4 << ' ' << y4 << endl;
}

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

int n;
string a;

int main () {
    cin >> n;
    cin >> a;
    for (int i = 0; i < a.length(); i++) {
	    int k = (a[i] - 'A' + n) % 26;
		a[i] = k + 'A'; 
	} 
	
	cout << a;
	
	return 0;
} 

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

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

Measured memory_bytes: 3568
n=int(input())
l=list(map(int,input().split()))
l.append(999)
a=l[0]
l.remove(a)
c=1
l2=[]
for i in l:
  if a==i:
    c+=1
  else:
    if c!=1:
      l2.append(c)
    c=1
  a=i
c2=0
for i in l2:
  c2+=i//2
print(c2)

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

int main() {
    size_t n, m;
    cin >> n >> m;
    vector<int> r( n );
    int a, b;
    for ( size_t i = 0; i < m; ++i ) {
        cin >> a >> b;
        ++r.at( a - 1 );
        ++r.at( b - 1 );
    }
    for ( size_t i = 0; i < n; ++i){
        cout << r.at( i ) << "\n"s;
    }
}

Measured memory_bytes: 256
s = gets.strip.chars
if s[0] != 'A'
  puts 'WA'
  exit
end
if s[2..-2].count('C') != 1
  puts 'WA'
  exit
else
    cnum = s.index('C')
end
(1..s.size-1).each do |i|
  if i != cnum
    if s[i] != s[i].downcase
      puts 'WA'
      exit
    end
  end
end 
puts 'AC' 


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

int main(){
  string ABCD;
  cin >> ABCD;
  vector<char> op(3);
  
  for (int i = 0; i < (1 << 3); i++) {
    int tmp = ABCD.at(0) - '0';
    for (int j=0; j<3; j++){
      if (i & 1<<j) {
        tmp += ABCD.at(j+1) - '0';
        op.at(j) = '+';
      }
      else {
        tmp -= ABCD.at(j+1) - '0';
        op.at(j) = '-';
      }
    }
  if (tmp == 7) break;
  }
    cout << ABCD.at(0);
    for (int k = 0; k < 3; k++){
     cout << op.at(k) << ABCD.at(k+1);
    }
    cout << "=7" << endl;
}

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

using namespace std;

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

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

bool isprime[125252];
bool is2017[125252];
int sum[125252];

int main(){
  isprime[0] = isprime[1] = false;
  FOR(x,2,125252){
    isprime[x] = true;
    for(int y=2;y*y<=x;y++)if(x%y==0){
      isprime[x] = false; break;
    }
  }
  REP(i,125252)is2017[i] = i%2==1 && isprime[i] && isprime[(i+1)/2];
  REP(i,125252)sum[i+1] = sum[i] + is2017[i];
  int q;
  scanf("%d",&q);
  while(q--){
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",sum[r+1]-sum[l]);
  }
  return 0;
}


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

#define INF 1e+9
#define MAX_V 2505

struct edge {
  int to;
  int cost;
};

using P = pair<int, int>;

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d, d+V, INF);
  d[s] = 0;
  que.push(P(0, s));

  while ( !que.empty() ) {
    P p = que.top();
    que.pop();
    int v = p.second;
    if (d[v] < p.first) { continue; }

    for ( int i = 0; i < G[v].size(); i++ ) {
      edge e = G[v][i];
      if ( d[e.to] > d[v] + e.cost ) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

int h, w;
int pos(int i, int j) { return i*w + j; }

int main() {
  cin >> h >> w;
  V = h * w;
  string table[h];
  for ( int i = 0; i < h; i++ ) { cin >> table[i]; }

  int black = 0;
  for ( int i = 0; i < h; i++ ) {
    for ( int j = 0; j < w; j++ ) {
      if ( table[i][j] == '#' ) { black++; continue; }
      if ( i+1 < h )  { G[pos(i,j)].push_back({pos(i+1,j), 1}); }
      if ( i-1 >= 0 ) { G[pos(i,j)].push_back({pos(i-1,j), 1}); }
      if ( j+1 < w )  { G[pos(i,j)].push_back({pos(i,j+1), 1}); }
      if ( j-1 >= 0 ) { G[pos(i,j)].push_back({pos(i,j-1), 1}); }
    }
  }

  dijkstra(pos(0,0));
  int ans = -1;
  if ( d[pos(h-1,w-1)] != INF ) {
    ans = h*w - d[pos(h-1,w-1)] - black - 1;
  }

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


Measured memory_bytes: 3784
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N, T, A = sc.nextInt()
  val (_, index) :: _ =
    List.fill(N)(sc.nextInt()).zipWithIndex.sortBy { case (h, _) => (A - T + h * 0.006).abs }
  println(index + 1)
}


Measured memory_bytes: 56016
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def resolve():
    V, E = iim()
    inf = float("inf")
    ad = [[inf]*V for i in range(V)]

    bi = [1<<i for i in range(V)]
    ans = 0
    odd = 0
    for i in range(E):
        s, t, d = iim()
        ad[s][t] = ad[t][s] = min(d, ad[s][t])

        odd ^= bi[s]
        odd ^= bi[t]
        ans += d

    if odd == 0:
        print(ans)
        return


    for _ in range(V):
        nochage = True
        for i in range(V):
            for j in range(i+1, V):
                for k in range(V):
                    d1 = ad[i][j]
                    d2 = ad[i][k] + ad[k][j]

                    if d1 > d2:
                        nochage = False
                        ad[i][j] = d2
                        ad[j][i] = d2
        if nochage:
            break

    v2 = [i for i in range(V) if odd & bi[i]]
    n2 = len(v2)
    dp = {0: 0}
    dk = [0]

    for i in range(n2):
        ii = bi[i]
        vi = v2[i]
        for j in range(i + 1, n2):
            jj = bi[j]
            vj = v2[j]

            for state in dk:
                ij = ii | jj
                if state & ij: continue

                st2 = state | ij
                co2 = dp[state] + ad[vi][vj]
                if st2 in dp:
                    if co2 < dp[st2]:
                        dp[st2] = co2
                else:
                    dp[st2] = co2
                    dk.append(st2)
    ans += dp[(1<<n2)-1]

    print(ans)


if __name__ == "__main__":
    resolve()



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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef set<ii> sii;
typedef set<int> si;
typedef priority_queue<int> pqi;
typedef priority_queue<ii> pqii;

const int INF = 1000000000;
const ll MOD = 1000000007;

int main() {FIN
	
	int w, h, n, x, y, a, xr, xl, yt, yb;
	cin >> w >> h >> n;
	xr = w, xl = 0, yt = h, yb = 0;
	while (n--) {
		cin >> x >> y >> a;
		if (a == 1) xl = max(xl, x);
		else if (a == 2) xr = min(xr, x);
		else if (a == 3) yb = max(yb, y);
		else yt = min(yt, y);
	}
	
	cout << (xl <= xr ? xr-xl : 0) * (yb <= yt ? yt-yb : 0) << "\n";
	
	return 0;
}


Measured memory_bytes: 3648
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    H,W = map(int, sys.stdin.readline().split())
    h2, w2 = map(int, sys.stdin.readline().split())
    n=(H-h2) * (W-w2)
    print(n)


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
int64_t rll() {
	long long n;
	scanf("%lld", &n);
	return n;
}

int64_t solve_gu(int n, int64_t *a) {
	std::priority_queue<int64_t> que;
	for (int i = 0; i < n; i++) que.push(a[i]);
	int64_t cur = 0;
	while (que.top() >= n - cur) {
		int64_t c = que.top();
		int64_t cnt = (c + cur + 1) / (n + 1);
		que.pop();
		que.push(c - (n + 1) * cnt);
		cur += cnt;
	}
	return cur;
}

int main() {
	int n = ri();
	int64_t a[n];
	for (int i = 0; i < n; i++) a[i] = rll();
	std::cout << solve_gu(n, a) << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define MAXN 200000

using namespace std;

int main(){
    int N,K;
    cin >> N >> K;
    int A[MAXN]={0};
    int cnt=0;
    for (int i=0;i<N;i++){
	int n;
	cin >> n;
	if (A[n]++ == 0) cnt++;
    }
    sort(A,A+MAXN,greater<int>());

    int ret=0;
    for (int i=cnt-1;i>K-1;i--){
	ret+=A[i];
    }

    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long

int main()
{
    int n,m,a,b,l=1,r=N;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        l=max(l,a);
        r=min(r,b);
    }
    printf("%d\n",min(n,max(0,r-l+1)));
    return 0;
}


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

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> start(n,0),end(n,0);
    for(int i = 0;i < m;i++){
        int a,b;
        cin >> a >> b;
        if(a == 1){
            start[b-1] = 1;
        }
        if(b == n){
            end[a-1] = 1;
        }
    }
    for(int i = 0;i < n;i++){
        if(start[i] == 1 && end[i] == 1){
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include<string>
#include<cmath>
#include<ciso646>
#include<cstring>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>



using ll = long long;
const int M = 1000005;


using namespace std;
int gcd(int a, int b) {
	if (a < b) {
		int t = a;
		a = b;
		b = t;
	}
	
	while (b != 0) {
		int t = b;
		b = a % b;
		a = t;
	}
	return a;
}

int factorial(ll n) {
	if (n > 0) {
		return n * factorial(n - 1);
	}
	else
		return 1;
}
int main()
{
	
	int n;
	cin >> n;
	vector<int> aa(n);
	vector<int> cnt(M);
	for (int i = 0;i < n;i++)
		cin >> aa[i];
	for (int x : aa) {
		//もうすでにダメな奴
		if (cnt[x] != 0) {

			cnt[x] = 2;
			continue;
		}
		for (int j = x;j < M;j += x) {
			//xの倍数にチェックをつける
			cnt[j]++;
		}
	}
	int ans = 0;
	for (int i : aa) {
		if (cnt[i] == 1) ans++;
	}
	cout << ans;
	
}
	
	



Measured memory_bytes: 8008
#include <stdio.h>
#include <string.h>
#define M 1000003
#define L 14

void Insert(char *);
int Find(char *);
int getChar(char );
int getKey(char *);
int h1(int);
int h2(int);

char H[M][L];

int main()
{
  int com_num,i;
  char command[9],str[L];

  for(int i =0; i < M; i++) H[i][0] = '\0';
  
  scanf("%d",&com_num);
  
  for(i = 0; i < com_num; i++){
    scanf("%s %s",command,str);
    if(command[0] == 'i') Insert(str);
    else{
      if(Find(str) == 1) printf("yes\n");
      else printf("no\n");
    }
  }
  return 0;
}


void Insert(char str[]){
  int i,n,key =  getKey(str);
  for(i = 0; i < M; i++){
    n = (h1(key)+i*h2(key))%M;
    if(H[n][0] == '\0'){
      strcpy(H[n],str);
      break;
    }
  }
}

int Find(char str[]){
  int i,n,key;
  key = getKey(str);
  for(i = 0; i < M ;i++){
    n = (h1(key)+i*h2(key))%M;
    if(strcmp(H[n],str) == 0) return 1;
    else if(strlen(H[n]) == 0) return 0;
  }
  return 0;
}

int getChar(char ch){
  if(ch == 'A') return 1;
  else if(ch == 'C') return 2;
  else if(ch == 'G') return 3;
  else if(ch == 'T')return 4;
  else return 0;
}

int getKey(char str[])
{
  int sum = 0,p = 1,i;
   for(i = 0; i < strlen(str); i++){
      sum+= p*(getChar(str[i]));
      p*=5;
    }
   return sum;
}

int h1(int key){
  return key%M;
}

int h2(int key){
  return 1 + (key%(M-1));
}



Measured memory_bytes: 15460
<?php
fscanf(STDIN, "%d%d", $H, $W);
for($i = 0; $i < $H; $i++){
  $str = fgets(STDIN);
  for($j = 0; $j < $W; $j++){
    $map[$i][$j] = $str[$j];
    $p[$i][$j] = 0;
  }
  $map[$i][$W] = "#";
}
for($j = 0; $j < $W; $j++){
  $map[$H][$j] = "#";
}
for($i = 0; $i < $H; $i++){
  $h = 0;
  for($j = 0; $j < $W+1; $j++){
    if($map[$i][$j] == "#"){
      for($k = 0; $k < $h; $k++){
        $p[$i][$j - 1 - $k] = $h;
      }
      $h = 0;
    }else{
      $h++;
    }
  }
}
for($i = 0; $i < $W; $i++){
  $h = 0;
  for($j = 0; $j < $H+1; $j++){
    if($map[$j][$i] == "#"){
      for($k = 0; $k < $h; $k++){
        $p[$j - 1 - $k][$i] += $h;
      }
      $h = 0;
    }else{
      $h++;
    }
  }
}
$max = 0;
for($i = 0; $i < $H; $i++){
  $max = max($max, max($p[$i]));
}
echo $max - 1;

Measured memory_bytes: 401912
#include <stdio.h>

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


}

int main() {
	int n, i, j, k;
	long long ans = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			for (k = 1; k <= n; k++) {
				ans += gcd(i,gcd(j,k));
			}
		}
	}
	printf("%lld", ans);

}

Measured memory_bytes: 1736
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[]str = Console.ReadLine().Split();
		int H = int.Parse(str[0]);
		int W = int.Parse(str[1]);
		int[,]A = new int[H,W];
		var list = new List<int>();
		for(var i=0;i<H;i++){
			string str2 = Console.ReadLine();
			for(var j=0;j<W;j++){
				if(str2.Substring(j,1)=="#"){
					A[i,j] = 1;
					list.Add(i*1000+j);
				}
			}
		}
		int max = 0;
		while(list.Count>0){
			var list2 = new List<int>(list);
			list.Clear();
			for(var i=0;i<list2.Count;i++){
				int x = list2[i]/1000;
				int y = list2[i]%1000;
				int ct = A[x,y];
				if(x>0){
					if(A[x-1,y]==0){
						A[x-1,y] = ct+1;
						max = Math.Max(max,ct);
						list.Add((x-1)*1000+y);
					}
				}
				if(x<H-1){
					if(A[x+1,y]==0){
						A[x+1,y] = ct+1;
						max = Math.Max(max,ct);
						list.Add((x+1)*1000+y);
					}
				}
				if(y>0){
					if(A[x,y-1]==0){
						A[x,y-1] = ct+1;
						max = Math.Max(max,ct);
						list.Add(x*1000+y-1);
					}
				}
				if(y<W-1){
					if(A[x,y+1]==0){
						A[x,y+1] = ct+1;
						max = Math.Max(max,ct);
						list.Add(x*1000+y+1);
					}
				}
			}
		}
		Console.WriteLine(max);
	}
}


Measured memory_bytes: 30920
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<string> vstring;
typedef vector<pint> vpint;
typedef stringstream SS;

struct Edge{int to,from,cost;};

#ifdef DEBUG
#define debug cout
#else
SS ss;
#define debug ss
#endif

template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

#define rep(i,n) for(int i=0;i<(n);++i)
#define repn(i,m,n) for(int i=(m);i<=(n);++i)
#define repd(i,n) for(int i=(n)-1;i>=0;--i)
#define repnd(i,m,n) for(int i=(n);i>=(m);--i)
#define rep0(i,n) for(i=0;i<(n);++i)
#define repn0(i,m,n) for(i=(m);i<=(n);++i)
#define repd0(i,n) for(i=(n)-1;i>=0;--i)
#define repnd0(i,m,n) for(i=(n);i>=(m);--i)
#define all(n) n.begin(),n.end()
#define sz(n) ((int)(n).size())
#define IL for(;;)
#define MP make_pair
#define PB push_back
#define X second
#define Y first
#define PUTLINE debug<<"LINE:"<<__LINE__<<endl;

const int INF = 2147483647/3;
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

int s[110][110];
int c[110][110];
int w,h;

bool isout(int y,int x){
	if(y<0||h<=y||x<0||w<=x)return true;
	return c[y][x]==1;
}

int main() {
	cin>>w>>h;
	rep(i,h)rep(j,w){
		cin>>s[i][j];
	}
	stack<pint> st;
	rep(i,h){
		st.push(MP(i,0));
		st.push(MP(i,w-1));
	}
	rep(i,w){
		st.push(MP(0,i));
		st.push(MP(h-1,i));
	}
	while(!st.empty()){
		pint now=st.top();
		st.pop();
		if(now.first<0||h<=now.first||now.second<0||w<=now.second)continue;
		if(s[now.first][now.second]==1)continue;
		if(c[now.first][now.second]==1)continue;
		c[now.first][now.second]=1;
		if(now.first%2==0){
			st.push(MP(now.first-1,now.second));
			st.push(MP(now.first-1,now.second+1));
			st.push(MP(now.first,now.second-1));
			st.push(MP(now.first,now.second+1));
			st.push(MP(now.first+1,now.second));
			st.push(MP(now.first+1,now.second+1));
		}else{
			st.push(MP(now.first-1,now.second-1));
			st.push(MP(now.first-1,now.second));
			st.push(MP(now.first,now.second-1));
			st.push(MP(now.first,now.second+1));
			st.push(MP(now.first+1,now.second-1));
			st.push(MP(now.first+1,now.second));
		}
	}
	int res=0;
	rep(i,h)rep(j,w){
		if(c[i][j]==1)continue;
		if(i%2==0){
			if(isout(i-1,j))++res;
			if(isout(i-1,j+1))++res;
			if(isout(i,j-1))++res;
			if(isout(i,j+1))++res;
			if(isout(i+1,j))++res;
			if(isout(i+1,j+1))++res;
		}else{
			if(isout(i-1,j-1))++res;
			if(isout(i-1,j))++res;
			if(isout(i,j-1))++res;
			if(isout(i,j+1))++res;
			if(isout(i+1,j-1))++res;
			if(isout(i+1,j))++res;
		}
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define pb push_back
#define mp make_pair

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

int A[3][111];

int main() {
  int n;
  S(n);
  rep(i,1,3) {
    rep(j,1,n+1) {
      S(A[i][j]);
      A[i][j] += max(A[i-1][j], A[i][j-1]);
    }
  }
  P(A[2][n]);
  return 0;
}


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


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

using namespace std;
using i32 = int;
using vi32 = vector<i32>;
using i64 = long long;
using vi64 = vector<i64>;

i64 n;
vi32 a;
vi64 c;

void add(int x) {
  while (x <= 2 * n) {
    c[x]++;
    x += x & -x;
  }
}

i64 sum(int x) {
  i64 s = 0;
  while (x) {
    s += c[x];
    x -= x & -x;
  }
  return s;
}

bool check(int md) {
  vi64 s(n + 1);
  c = vi64(n * 3);
  rep(i, n) {
    if (a[i] >= md)
      s[i + 1] = s[i] + 1;
    else
      s[i + 1] = s[i] - 1;
  }
  i64 cnt = 0;
  rep(i, n + 1) {
    cnt += sum(s[i] + n);
    add(s[i] + n);
  }
  return cnt >= n * (n + 1) / 4;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  cerr << fixed << setprecision(16);
  cin >> n;
  a = vi32(n);
  rep(i, n) cin >> a[i];
  int ok = *min_element(all(a)), ng = *max_element(all(a)) + 1;
  while (ng - ok > 1) {
    int md = (ok + ng) / 2;
    if (check(md)) {
      ok = md;
    } else {
      ng = md;
    }
  }
  cout << ok << endl;
  return 0;
}


Measured memory_bytes: 6176
<?php 
$n = trim(fgets(STDIN));
if($n <= 1000){
  echo 1000 - $n;
}else{
while($n >= 1000){
  $n -= 1000;
}
  if($n == 0){
	echo $n;
  }else{
    echo 1000 - $n;
  }
}

Measured memory_bytes: 16180
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ld> pid;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	vector<pid> v;
	REP(i, 16)REP(j, 1000)
	{
		ll t = j * pow(10, i);
		REP(k, i) t += 9 * pow(10, k);

		ll s = 0;
		ll tmp = t;
		while (tmp > 0)
		{
			s += tmp % 10;
			tmp /= 10;
		}
		v.emplace_back(t, t / ld(s));
	}
	sort(v.rbegin(), v.rend());
	vector<ll> ans;

	ld mn = v[0].second;
	REP(i, v.size())
	{
		if (v[i].second <= mn)
		{
			ans.push_back(v[i].first);
			mn = v[i].second;
		}
	}
	sort(ALL(ans));
	unique(ALL(ans));
	int k; cin >> k;
	REP(i, k) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 1020
#include <iostream>
#include <stdlib.h>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
map<string, int> dp;
int direction[4] = { 1,-1,4,-4 };
void bfs() {
	queue <string> que;
	que.push("01234567");
	while (!que.empty())
	{
		string now = que.front();
		que.pop();
		int p = 0;
		for (int j = 0; j < 8; j++) {
			if (now[j] == '0') {
				p = j;
				break;
			}
		}
		for (int i = 0; i < 4; i++) {
			int n = p + direction[i];
			if (0 <= n && n < 8 && !(p == 3 && n == 4) && !(p == 4 && n == 3)) {
				string next = now;
				swap(next[p], next[n]);
				if (dp.find(next) == dp.end()) {
					dp[next] = dp[now] + 1;
					que.push(next);
				}

			}
		}

	}

}

int main(int argc, char *argv[])
{

	bfs();
	string line;
	while (getline(cin, line))
	{
		line.erase(remove(line.begin(), line.end(), ' '), line.end());
		cout << dp[line] << endl;
	}

	return 0;
}
///////////////////////////End Sub//////////////////////////////////



Measured memory_bytes: 5260
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	var p = make([]int, n)
	var tmp = make([]int, n)
	for i := range p {
		fmt.Scan(&p[i])
		tmp[i] = p[i]
	}

	sort.Ints(p)
	count := 0
	for i, v := range p {
		if tmp[i] != v {
			count++
		}
	}
	if count == 2 || count == 0 {
		fmt.Println("YES")
		return
	}
	fmt.Println("NO")
}


Measured memory_bytes: 512
// ~/Remember,remember the 6th of March

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double  EPS = 1e-8;
const ll MOD = 1000000007;
const int N = 100000 + 7;

int main()
{
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int &i:arr)cin>>i;
    ll ans =2e18;
    ll res=0;
    for(int i=1;i<101;i++){
        res=0;
        for(int j=0;j<n;j++)
            res+=(arr[j]-i)*(arr[j]-i);
        ans=min(ans,res);
    }
    cout<<ans<<endl;
    return 0;
}





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

int main(void)
{
	int i, j, l;
	int count = 0;
	int n, m;
	scanf("%d %d", &n, &m);

	char N[100][100];
	char M[100][100];

	for (i = 0; i < n; i++)
		scanf("%s", N[i]);
	for (i = 0; i < m; i++)
		scanf("%s", M[i]);

	if (n >= m)
		for (i = 0; i < n-m+1; i++)
		{
				for (j = 0; j < n-m+1; j++)
				{
					if (strncmp(N[i]+j, M[0], m) == 0)
					{
						count++;
						for (l = i+1 ; l < m+i; l++)
						{
							if (strncmp(N[l]+j, M[l-i], m) == 0)
								count++;
						}

						if (count == m)
						{
							printf("Yes"); return 0;
						}
						count = 0;
					}
				}
		}

	else if (m >= n)
		for (i = 0; i < m-n+1; i++)
		{
				for (j = 0; j < m-n+1; j++)
				{
					if (strncmp(N[i]+j, M[0], n) == 0)
					{
						count++;
						for (l = i+1 ; l < n+i; l++)
						{
							if (strncmp(N[l]+j, M[l-i], n) == 0)
								count++;
						}

						if (count == n)
						{
							printf("Yes"); return 0;
						}
						count = 0;
					}
				}
		}

	printf("No");

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
typedef long long ll;
const int INF = 1000000000;
const long INF64 = 1000000000000000ll;
const ll MOD = 1000000007ll;
int a,b,x;
int main(){
    std::cin >> x>>a>>b;
    if(a>=b){
        std::cout << "delicious" << std::endl;
    }else if(b-a<=x){
        std::cout << "safe" << std::endl;
    }else{
        std::cout << "dangerous" << std::endl;
    }
}


Measured memory_bytes: 256