akhauriyash/Code-Regression huggingface dataset:
/**
*    author:  yuya1234
*    created: 13.07.2020 15:15:12
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define FORV(i,v) for(auto i=v.begin(); i!=v.end();i++)

#define SORT(s) sort((s).begin(),(s).end())
#define SORTD(s) sort((s).rbegin(),(s).rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define SZ(x) ((int)(x).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))

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 gcd(int a,int b){return b?gcd(b,a%b):a;}

ll calc(ll n){
  if(n==0) return 0;
  return calc(n-1)+n;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  //std::cout << std::fixed << std::setprecision(15);

  int n;
  cin>>n;

  string s[n];
  string tmp;
  vector<string> v;
  REP(i,n){
    cin>>tmp;
    SORT(tmp);
    s[i]=tmp;
  }

  sort(s,s+n);

  ll ans=0,cnt;
  REP(i,n){
    cnt=0;
    FOR(j,i+1,n){
      if(s[i]==s[j])cnt++;
      else break;
    }
    if(cnt>0)ans+=calc(cnt);
    i+=cnt;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 6716
#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
//#define int unsigned long long
#define all(x) (x).begin(), (x).end()
#define double long double

using namespace std;

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 MOD = 1e9 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;



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

	int N, K; cin >> N >> K;
	print((N+2*K)/(2*K+1));

}


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

sort(a,a+n,[](int x,int y){
return x<y;
});


*/





void solve(){


int l,r,d;

cin>>l>>r>>d;


int k= r/d-l/d+(l%d==0);

cout<<k<<endl;







}


int main() {

int t;
t=1;


while(t-->0){



solve();
}



return 0;
}

Measured memory_bytes: 3616
#include "bits/stdc++.h"

using namespace std;

void Main() {
    int N, A;
    cin >> N;
    cin >> A;

    cout << (A >= N % 500 ? "Yes" : "No") << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3620
ary = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
puts ary[gets.chomp.to_i - 1]

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

#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int main(){
	fastio
	char c;
	cin >> c;
	if(c == toupper(c)){
		cout << "A" << "\n";
	}else{
		cout << "a" << "\n";
	}
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

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

int main() {
	init();

	int H, W; cin >> H >> W;
	vector<string>vec(H);
	rep(i, 0, H)cin >> vec[i];
	bool is = true;
	rep(i, 0, H) {
		rep(j, 0, W) {
			bool ok = false;
			if (vec[i][j] != '#')continue;
			rep(k, 0, 4) {
				int ny = i + dy[k], nx = j + dx[k];
				if (out(ny, nx, H, W))continue;
				if (vec[ny][nx] == '#')ok = true;
			}
			if (!ok) {
				is = false;
			}
		}
	}
	cout << (is ? "Yes" : "No") << "\n";

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
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(){
    int H,W,N;cin>>H>>W>>N;
    vector<int>color(N);
    vector<int>C(H*W);
    int k=0;
    rep(i,N){
        cin>>color[i];
        for(int j=k;j<k+color[i];j++){
            C[j]=i+1;
        }
        k=k+color[i];
    }
    Graph CC(H,vector<int>(W));
    int count=0;
    rep(i,H){
        rep(j,W){
            count++;
            CC[i][j]=C[count-1];
        }
    }
    rep(i,H){
        if(i%2==1){
            reverse(CC[i].begin(),CC[i].end());    
        }
        rep(j,W){
            if(j==W-1){
                cout<<CC[i][j]<<endl;
            }
            else{
                cout<<CC[i][j]<<" ";
            }
        }
    }
}

Measured memory_bytes: 384
package main

import "fmt"

func main() {
	var a, b int
	fmt.Scan(&a, &b)
	if a+b == 15 {
		fmt.Println("+")
	} else if a*b == 15 {
		fmt.Println("*")
	} else {
		fmt.Println("x")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
#define endl '\n'
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; }
using namespace std;

class Union_Find{
private:
    vector<int> par;
    vector<int> rank;
public:
    Union_Find(int n){
        rep(i,n){
            par.push_back(i);
            rank.push_back(0);
        }
    }
    int find(int x){
        if(par.at(x)==x) return x;
        else return par.at(x)=find(par.at(x));
    }
    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank.at(x)<rank.at(y)){
            par.at(x)=y;
        }else{
            par.at(y)=x;
            if(rank.at(x)==rank.at(y)) rank.at(x)++;
        }
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
};

signed main(){
    int n,m; cin>>n>>m;
    vector<int> a(n),x(m),y(m);
    rep(i,n){
        cin>>a.at(i);
        a.at(i)--;
    }
    Union_Find uni(n);
    rep(i,m){
        cin>>x.at(i)>>y.at(i);
        x.at(i)--; y.at(i)--;
        uni.unite(x.at(i), y.at(i));
    }
    vector<vector<P>> gr(n,vector<P>(0));
    rep(i,n){
        gr.at(uni.find(i)).push_back(P(i,a.at(i)));
    }
    int ans=0;
    rep(i,n){
        if(gr.at(i).size()==0)continue;
        map<int,int> mp;
        rep(j,gr.at(i).size()){
            mp[gr.at(i).at(j).F]++;
        }
        rep(j,gr.at(i).size()){
            if(mp[gr.at(i).at(j).S]>0){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 14312
import java.util.Scanner; 
public class Main {
 
    public static void main (String[] args){
     Scanner scanner = new Scanner(System.in);  
     int n = scanner.nextInt();
     
      switch(n % 10){
        case 2:
        case 4:
        case 5:
        case 7:
        case 9:
        	System.out.println("hon");
       		 break;
        case 0:
        case 1:
        case 6:
        case 8:
        	System.out.println("pon");
        	break;
        case 3:
        	System.out.println("bon");
        	break;
      }
    }
  
}

Measured memory_bytes: 27048
#include <stdio.h>

int main(){

    int num1,num2,n;
    int ctr = 0;
    scanf("%d %d %d", &num1, &num2, &n);

    for( int i = num1; i <= num2; i++){
        if(i % n == 0){
            ctr++;
        }
    }
    printf("%d", ctr);


    return 0;
}

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

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define MOD 1000000007

const int MAX_M = 100000;


int main(){
  ll a, b, c, k;    //n枚,y円
  //string s, t;
  cin >> a >> b >> c >> k;

  //vector<ll> a(n);
  //queue<ll> q;
  //map<string,ll> m;

  ll ans = 0;

  if(k<=a){
    ans+=k;
  }

  else{
    ans+= a;
    k -= a;

    k -= b;

    if(k>=0){
      ans-=k;
    }
  }



  //cout << fixed << setprecision(10);
  cout << ans << endl;
  //cout << ((ok)? "Yes" : "No") << endl;

}


Measured memory_bytes: 3552
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
  string a,b,c;
  cin>>a>>b>>c;
  if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0]){
    cout<<"YES"<<endl;  
  }else{
    cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 256
sx,sy,tx,ty = map(int,input().split(' '))
w,h = abs(sx-tx),abs(sy-ty)

res = 'U'*h+'R'*w+'D'*h+'L'*w
res += 'L'+'U'*(h+1)+'R'*(w+1)+'DR'+'D'*(h+1)+'L'*(w+1)+'U'
print(res)

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main()
{
    int x;
    cin>>x;
    if(x>=400 && x<=599)
    {
        cout<<8<<endl;
    }
    else if(x>=600 && x<=799)
    {
        cout<<7<<endl;
    }
    else if(x>=800 && x<=999)
    {
        cout<<6<<endl;
    }
    else if(x>=1000 && x<=1199)
    {
        cout<<5<<endl;
    }
    else if(x>=1200 && x<=1399)
    {
        cout<<4<<endl;
    }
    else if(x>=1400 && x<=1599)
    {
        cout<<3<<endl;
    }
    else if(x>=1600 && x<=1799)
    {
        cout<<2<<endl;
    }
    else 
    {
        cout<<1<<endl;
    }
    return 0;
}

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

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

    int n;
    cin >> n;

    vector<int> s(n);
    REP(i, n) cin >> s[i];

    vector<vector<bool> > dp(n + 1, vector<bool>(10001, false));

    dp[0][0] = true;

    REP(i, n) REP(j, 10001) {
        if (dp[i][j]) {
            dp[i + 1][j] = true;
            dp[i + 1][j + s[i]] = true;
        }
    }

    int ans = 0;
    REP(i, 10001)
        if (i % 10 && dp[n][i])
            ans = max(ans, i);

    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 384
/*________________________Bismillahir Rahmanir Rahim___________________
|                                                                      |
|                    /\     |     | |\    |     /\     |-------        |
|                   /  \    |     | | \   |    /  \    |               |
|                  /----\   |-----| |  \  |   /----\   |-----          |
|                 /      \  |     | |   \ |  /      \  |               |
|                /        \ |     | |    \| /        \ |               |
|                     14th batch CSE , ID : 12008029                   |
|                     Comilla University                               |
|                     Email : sheikhahnafshifat@gmail.com              |
|______________________________________________________________________*/
#include<bits/stdc++.h>
#include<string>
#include<iostream>
using namespace std;
#define ll                      long long
#define MAX                     1000007
#define pb(x)                   push_back(x)
#define mp(x,y)                 make_pair(x,y)
#define vii                     vector<int>
#define vll                     vector<long long>
#define vp                      vector<pair<ll, ll> >
#define v_min(a)                *min_element(a.begin(),a.end())
#define v_max(a)                *max_element(a.begin(),a.end())
#define v_sum(a)                accumulate(a.begin(),a.end(),0)
#define un(a)                   a.erase(unique(a.begin(),a.end()),a.end())
#define SORT(a)                 sort(a.begin(),a.end())
#define AHNAF                   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define gcd(a,b)                __gcd(a,b)
#define lcm(a,b)                ((a)*(b))/gcd(a,b)
#define YES                     cout<<"YES"<<endl
#define NO                      cout<<"NO"<<endl
#define testcase(t)             int t;cin>>t;while(t--)
#define reverse(a)              reverse(a.begin(),a.end())
#define ff                      first
#define ss                      second
#define print(a)                for(auto it: a) cout<<it<<" "
///--------------Graph Moves--------------------------------------
///const int fx[] = {+1,-1,+0,+0};
///const int fy[] = {+0,+0,+1,-1};
///const int fx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's move
///const int fy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
///const int fx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's move
///const int fy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's move
///---------------------------------------------------------------

int main()
{
    AHNAF;
    int n;
    cin>>n;
    vll v(n);
    for(int i=0; i<n; i++)
        cin>>v[i];
    int cnt=0;//SORT(v);un(v);
    for(int i=0; i<v.size(); i++)
    {
        for(int j=i+1; j<v.size(); j++)
        {
            for(int k=j+1; k<v.size(); k++)
            {
                if(v[i]!=v[j]&&v[i]!=v[k]&&v[j]!=v[k])
            {
                if(v[i]+v[j]>v[k]&&v[i]+v[k]>v[j]&&v[j]+v[k]>v[i])
                    cnt++;
            }
            }
        }
    }
    cout<<cnt;
}




Measured memory_bytes: 3668
import itertools
from math import factorial

N=int(input())
x=[0]*N
y=[0]*N
path=[0]*(factorial(N))
for i in range(N):
  x[i],y[i] = map(int,input().split())
  
L=list( itertools.permutations([i for i in range(N)]) )
for j,order in enumerate(L):
  for k in range(1,len(order)):
    path[j] += ( (x[order[k]]-x[order[k-1]])**2 + (y[order[k]]-y[order[k-1]])**2 )**0.5
  #print(j,order,path[j])
    
print(sum(path)/len(path))
#  for i,k in enumerate(order):
#    if i==0:
#      pass
#    else:
#      path[j] += 

Measured memory_bytes: 9252
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define itrep(it, a) for(it = (a).begin(); it != (a).end(); it++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 30)
using namespace std;

#define N 105

bool check(int M[N]){
    int cnt = 0;
    range(i,3,N) if(M[i] % 2 == 1) return false;

    return true;
}

int main(){
    int a, b;
    while(cin >> a >> b){
        int M[N] = {0};
        M[a]++; M[b]++;
        while(cin >> a >> b, a||b){
            M[a]++; M[b]++;
        }
        if(check(M)){
            if(M[1] % 2 == 1 && M[2] % 2 == 1) cout << "OK" << endl;
            else cout << "NG" << endl;
        } else cout << "NG" << endl;
    }
}

Measured memory_bytes: 1156
module.exports=function(r){var t={};function e(n){if(t[n])return t[n].exports;var o=t[n]={i:n,l:!1,exports:{}};return r[n].call(o.exports,o,o.exports,e),o.l=!0,o.exports}return e.m=r,e.c=t,e.d=function(r,t,n){e.o(r,t)||Object.defineProperty(r,t,{enumerable:!0,get:n})},e.r=function(r){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(r,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(r,"__esModule",{value:!0})},e.t=function(r,t){if(1&t&&(r=e(r)),8&t)return r;if(4&t&&"object"==typeof r&&r&&r.__esModule)return r;var n=Object.create(null);if(e.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:r}),2&t&&"string"!=typeof r)for(var o in r)e.d(n,o,function(t){return r[t]}.bind(null,o));return n},e.n=function(r){var t=r&&r.__esModule?function(){return r.default}:function(){return r};return e.d(t,"a",t),t},e.o=function(r,t){return Object.prototype.hasOwnProperty.call(r,t)},e.p="",e(e.s=0)}([function(r,t,e){e(1)(e(2).readFileSync("/dev/stdin","UTF-8"))},function(r,t){function e(r,t){return function(r){if(Array.isArray(r))return r}(r)||function(r,t){var e=[],n=!0,o=!1,u=void 0;try{for(var i,f=r[Symbol.iterator]();!(n=(i=f.next()).done)&&(e.push(i.value),!t||e.length!==t);n=!0);}catch(r){o=!0,u=r}finally{try{n||null==f.return||f.return()}finally{if(o)throw u}}return e}(r,t)||function(){throw new TypeError("Invalid attempt to destructure non-iterable instance")}()}r.exports=function(r){for(var t=r.split("\n"),n=e(t[0].split(" ").map(function(r){return Number(r)}),2),o=n[0],u=n[1],i=[],f=0;f<o;f++){var l=t[1+f].split(" ").map(function(r){return Number(r)});i.push(l)}for(var a=0,c=0;c<o;c++)for(var p=o-1;p>c;p--){for(var s=0,d=0;d<u;d++)s+=(i[c][d]-i[p][d])*(i[c][d]-i[p][d]);Math.sqrt(s)%1==0&&(a+=1)}console.log(a)}},function(r,t){r.exports=require("fs")}]);

Measured memory_bytes: 7372
import numpy as np
h, n = map(int, input().split())    
ab = np.array([tuple(map(int, input().split())) for _ in range(n)])
dp = np.zeros(h + 1, dtype="int")
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
print(dp[-1])

Measured memory_bytes: 12516
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(M)]

start = 10 ** (N - 1)
if start == 1: start = 0
end = 10 ** N

for i in range(start, end):
  t = str(i)
  c = True
  
  for j in range(M):
    if t[sc[j][0] - 1] != str(sc[j][1]):
      c = False
      
  if c:
    print(t)
    exit()
    
print('-1')

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <cassert>

using namespace std;
typedef long long ll;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int odd = (n + 1) / 2;
  double res = odd / (1.0 * n);
  cout << setprecision(9) << fixed << res << endl;
  return 0;
}


Measured memory_bytes: 3716
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int N,M; cin >> N >> M;
    vector<int> num(N,1);
    vector<bool> red(N,false);
    red[0] = true;

    int x,y;
    for(int i=0;i<M;i++){
        cin >> x >> y;
        x--; y--;
        if(red[x]) red[y] = true;
        num[x]--; num[y]++;
        if(num[x] == 0) red[x] = false;
    }

    int ans = 0;
    for(int i=0;i<N;i++){
        if(red[i]) ans++;
    }

    cout << ans << endl;

    return 0;
}

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

int n, m;
map<int, int> mp;
int a[100005];
 
int main()
{
	string s;
	cin >> n >> m;
	
	for(int i = 0; i < n; i++)
		cin >> a[i];
	
	sort(a, a + n);
	
	int x, y;
	
	for(int i = 0; i < m; i++)
	{
		cin >> x >> y;
		mp[y] += x;
	}
	
	long long ans = 0;
	
	for(int i = 0; i < n; i++)
	{
		if(mp.size() && mp.rbegin() -> first > a[i])
		{
			a[i] = mp.rbegin() -> first;
			mp.rbegin() -> second--;
			
			if(mp.rbegin() -> second == 0)
				mp.erase(mp.rbegin() -> first);
		}
		
		ans += a[i];
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5376
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e18;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }
int n, a, b, c;
vector<int> l;
int dfs(int cur, int A, int B, int C) {
  if (cur == n) return (A == 0 || B == 0 || C == 0) ? INF : abs(A - a) + abs(B - b) + abs(C - c) - 30;
  int w = dfs(cur + 1, A, B, C);
  int x = dfs(cur + 1, A + l[cur], B, C) + 10;
  int y = dfs(cur + 1, A, B + l[cur], C) + 10;
  int z = dfs(cur + 1, A, B, C + l[cur]) + 10;
  return min(min(min(w, x), y), z);
}

signed main() {
  cin >> n >> a >> b >> c;
  l.resize(n);
  rep(i, n) cin >> l[i];
  cout << dfs(0, 0, 0, 0) << endl;
  return 0;
}


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

uli ans=-1;
uli n,s;
void solve(uli b){
   if(b<2)return;
   uli x=n;
   uli sd=0;
   while(x!=0){
      sd+=x%b;
      x/=b;
   }
   if(sd==s){
      if(ans==-1 || b<ans)ans=b;
   }
}
int main(){
   cin>>n>>s;
   if(n==s){
      cout<<n+1<<endl;
      return 0;
   }
   if(n==1){
      puts("-1");
      return 0;
   }
   for(uli x=1;x*x<=n-s;x++)if((n-s)%x==0){
      uli y=(n-s)/x;
      solve(x+1);
      solve(y+1);
   }
   printf("%lld\n",ans);
   return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main( void ) {

	int a[4], b[4], i, j, hit, blow;

	while ( scanf( "%d %d %d %d %d %d %d %d", &a[0], &a[1], &a[2], &a[3], &b[0], &b[1], &b[2], &b[3] ) != EOF ) {

		hit = 0; blow = 0;

		for ( i = 0; i < 4; i++ ) {

			for ( j = 0; j < 4; j++ ) {

				if ( a[i] == b[j] ) {

					if ( i == j ) { hit++; }
					else { blow++; }

				}

			}

		}

		printf( "%d %d\n", hit, blow );

	}

	return 0;

}

Measured memory_bytes: 596
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)

ds = {}
def sub(u):
    if u in ds:
        return ds[u]
    d = 0
    for v in ns[u]:
        d = max(d, sub(v)+1)
    ds[u] = d
    return d

for i in range(n):
    if i not in ds:
        sub(i)
print(max(ds.values()))

Measured memory_bytes: 239264
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;cin>>s;
	reverse(s.begin(), s.end());
	int n = s.size();
	int pref[n], mod = 2019, ten = 1;
	pref[0] = s[0] - '0';
	map<int, ll> mp;
	mp[0] = 1;
	mp[pref[0]] = 1;
	for(int i = 1; i < n; ++i){
		ten*=10;
		ten%=mod;
		pref[i] = pref[i-1] + ten*(s[i]-'0');
		pref[i] %= mod;
		mp[pref[i]]++;
	}
	ll cnt = 0;
	for(auto x : mp){
		cnt += (x.second-1)*x.second/2;
	}
	cout<<cnt<<endl;
	return 0;
}



Measured memory_bytes: 4572
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
string a;
int main() {
	cin>>a;
	int l=a.length();
	for(int i=0;i<l;i++){
		if(i%2==0) printf("%c",a[i]);
	}
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin>>N;
  int sum=0;
  for(int i=0;i<N;i++){
    int a;
    int b;
    cin>>a>>b;
    sum+=b-a+1;
  }
  cout<<sum<<endl;

}


Measured memory_bytes: 3664
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
int main() {

	string O, E;
	cin >> O >> E;

	for (int i = 0; i < E.length(); i++) {
		cout << O[i] << E[i];
	}

	if (O.length() > E.length()) {
		cout << O[O.length() - 1];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
using Graph = vector<vector<int>>;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -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;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}

const string st[3] = {"3","5","7"} ;


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n ;
  cin >> n ;
  queue<string> Q ;
  vector<string> str ;
  
  Q.push("3") ;
  Q.push("5") ;
  Q.push("7") ;
  
  while(!Q.empty()){
    string s = Q.front() ;
    str.PB(s) ;
    Q.pop() ;
    if(SZ(s)<9){
      REP(i,3){
        string t = s+ st[i] ;
        Q.push(t) ;
      }
    }
  }
  
  vint num ;
  
  REP(i,SZ(str)){
    set<char> S ;
    REP(j,SZ(str[i])){
      S.insert(str[i][j]) ;
    }
    if(SZ(S)==3){
      num.PB(stoi(str[i])) ;
    }
  }
  
  sort(ALL(num)) ;
  auto iter_lower = lower_bound(num.begin(), num.end(), n);
  int idx_lower = distance(num.begin(), iter_lower);
  
  if(binary_search(ALL(num),n)){
    idx_lower++ ;
  }
  cout << idx_lower <<endl ;
      
      
  
    
      
  
    
  
  
  
  
  return 0 ;
}

Measured memory_bytes: 2556
//shara's here
#include <bits/stdc++.h>
using namespace std;
typedef int q;
typedef double w;
typedef string s;
typedef long long ll;
int main(){
    q x,y;
    cin>>x>>y;
    if((x==1||y==1)&&(x==2||y==2)){cout<<3;}
    else if((x==1||y==1)&&(x==3||y==3)){cout<<2;}
    else if((x==2||y==2)&&(x==3||y==3)){cout<<1;}












return 0;}
/*
███████████████████████████████████████████████████
███████████████████████████████████████████████████
██████████████████████████████████▀████████████████
██████████████████████████████████░▀███████████████
██████████████████████████████▌███░░░▀▀████████████
██▀████████████████████▐██████░▐██░░░░░░▀▀█████████
██░████████████████████▐█████▌░██▌▄░░░░▄▄░▄████▀███
█▌░███████████████████▀░█████░░░█░░░▄████░░███▀▐███
█▌░▐██████████████████░░████▌░░░▀░░▀███▀▀░▐███▄████
██░▀██████████████▌▐█▐▄▄████▌░░░░░░░░░░░░░▌████████
███░███████████████▀░▄▄██▀█▐░░░░░░░░░░░░░░▐████████
███▄░██████████████▄░░░░░░▀▀▀░░░░░░░░░░░░░█▐███████
████▄░██████████████████▄▄▄▄▄▄▐▄░░░░░░░░░░░████████
█████▄█████████████████▀▀▀▀▀▀░░░░░░░░░░░░░░████████
████████████████████████▄░░░░░░░░░░░░░░░▄░░████████
██████████████████████████▄▄▄░░░░░░░░░▄█░▄█████████
████████████████████████████████▄░░░░██▄███▀░░▀████
█████████████████████████████▀█████▄███▀▀▀░░▄▄░████
████████████████████████████▀░░▀░░▀▀░░░░▄▄▄██▀░░▀▀█
███████████████████████████▌░░░░░░░░░░░███████░░░▄█
███████████████▄░▀████████▀░░░░░░▀░░░░███████▌░░░██
███▄▄████████████▄░▀██████▄░░░░░█░░░░████████░░░▀▀
░▀█████████████████▄░▀█████░░░░██░░░░▀██████░░░░░▄█
▐█▄▀█████████████████▄░▀████░░░██▌░░░▐████▀░░░░▄███
▐███▄▀▀█████████████████▄░▀▀░░░░▀██▌▄█▀▀░░░▄▄██████
▀▀▀▀▀░░░▀▀▀▀▀░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░▀▀░░░░░░▀▀▀▀▀▀▀▀▀
*/


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

typedef int in;
#define int long long
int MAX=1e8;

int n,w;
int a[100005],b[100005],dp[105][100005];

int f(int idx,int rem)
{
    if(idx==n)
        return 0;
    int &ret=dp[idx][rem];
    if(ret!=-1)
        return ret;
    ret=f(idx+1,rem);
    if(rem-b[idx]>=0)
        ret=max(ret,f(idx+1,rem-b[idx])+a[idx]);
    return ret;
}

in main()
{
    int tc=1;
//    cin>>tc;
    while(tc--)
    {
        cin>>n>>w;
        for(int i=0; i<n; i++)
        {
            cin>>b[i]>>a[i];
        }
        memset(dp,-1,sizeof dp);
        cout<<f(0,w);
    }
    return 0;
}


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

int main(){
    int size, i, flag = 1;
    char string[101];
    scanf("%d ", &size);
    scanf("%s", string);
    if(size%2){
        flag = 0;
    }else{
        for(i=0; i<size/2; i++){
            if(string[i] != string[i+size/2]){
                flag = 0;
                break;
            }
        }
    }
    if(flag){
        printf("Yes");
    }else{
        printf("No");
    }
    return 0;
}

Measured memory_bytes: 128
S = input()
n = int(S[:2])
m = int(S[2:])
flgs = [0, 0]
if 0 < n and n < 13:
  flgs[0] = 1
if 0 < m and m < 13:
  flgs[1] = 1
if flgs[0]:
  if flgs[1]:
    print('AMBIGUOUS')
  else:
    print('MMYY')
else:
  if flgs[1]:
    print('YYMM')
  else:
    print('NA')

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <random>

#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a)-1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a)-1; (i) >= (b); (i)--)
#define PI acos(-1.0)
#define DEBUG(C) cerr << C << endl;
#define VI vector <int>
#define VII vector <VI>
#define VL vector <LL>
#define VLL vector <VL>
#define VD vector <double>
#define VDD vector <VD>
#define PII pair <int, int>
#define PDD pair <double, double>
#define PLL pair <LL, LL>
#define VPII vector <PII>
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define REVERSE(a) reverse(ALL(a))
#define MP make_pair
#define EB emplace_back
#define FORE(a, b) for (auto &&a : b)
#define FIND(s, n) (s.find(n) != s.end())

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int N; cin >> N;
    VI A(N);
    REP(i, N) scanf("%d", &A[i]);
    int minnum = 2;
    LL ans = A[0] - 1;
    FOR(i, 1, N) {
        if (A[i] == minnum) {
            minnum++;
            continue;
        }
        if (A[i] % minnum == 0) {
            ans += (A[i] / minnum) - 1;
        } else {
            ans += A[i] / minnum;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
n, l = map(int, input().split())
taste = []
for i in range(1, n + 1):
    taste.append(l + i - 1)

max_pie = sum(taste)

min_diff = 10 ** 9
second_pie = 10 ** 9
for i in range(n):
    small_pie = sum(taste[:i]) + sum(taste[i + 1:])
    diff = abs(small_pie - max_pie)
    if diff < min_diff:
        min_diff = diff
        second_pie = small_pie
print(second_pie)


Measured memory_bytes: 3060
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
ans=0
while(True):
    flag=0
    #print(B)
    for i in range(N):
        tmp=B[(i-1)%N]+B[(i+1)%N]
        if B[i]>tmp>0 and B[i]>A[i]:
            beforeans=ans
            if B[i]%tmp>=A[i]:
                ans+=B[i]//tmp
                B[i]%=tmp
            else:
                k=((A[i]-1-(B[i]%tmp))//tmp)+1
                ans+=B[i]//tmp
                B[i]%=tmp
                #print(i,1,B)
                ans-=k
                B[i]+=k*tmp
                #print(i,2,B)
            if ans!=beforeans:
                flag=1
    if flag==0:
        break
flag2=1
for i in range(N):
    if A[i]!=B[i]:
        flag2=0
        break
if flag2:
    print(ans)
else:
    print(-1)


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

int main(){
  int n;
  int s[12];
  int tmp[12];
  int ans;
  int flag;

  while(1){
    cin >> n;
    if(!n)break;

    ans = 0;
    for(int i=0;i<n;i++)cin >> s[i];

    while(1){

      for(int i=0;i<n;i++){
	int c = 0;
	for(int j=0;j<n;j++)if(s[i] == s[j])c++;
	tmp[i] = c;
      }

      flag = 1;
      for(int i=0;i<n;i++)if(s[i] != tmp[i])flag=0;
    
      if(flag)break;
      else {
	ans++;
	for(int i=0;i<n;i++)s[i] = tmp[i];
      }
    }

    cout << ans << endl;
    for(int i=0;i<n-1;i++)cout << s[i] << " ";
    cout << s[n-1] << endl;
  }
}

Measured memory_bytes: 0
// AtCoder ABC064 B - Traveling AtCoDeer Problem
// 2020.1.25 bal4u

#include <stdio.h>

#define gc() getchar_unlocked()

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

int main()
{
	int N, mi, ma, a;
	
	N = in();
	mi = ma = in();
	while (--N) {
		a = in();
		if (a < mi) mi = a;
		else if (a > ma) ma = a;
	}
	printf("%d\n", ma-mi);
	return 0;
}


Measured memory_bytes: 128
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (n);i++)
using ll = long long;
const ll MOD=1000000007;
const double pi=acos(-1);





int main() 
{
  ll N,M,K; cin>>N>>M>>K;
  rep(i,N+1)
  {
    rep(j,M+1)
    {
      if(i*j+(N-i)*(M-j)==K) {cout<<"Yes"<<endl; return 0;}
    }
  }
  cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<map>
#define mod 1000000007
#define rep(i,N) for(int i=0;i<N;i++)
using namespace std;

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

int main(){
    int n;
    int ans;
    cin>>n;
    vector<int> a(100000,0);
    cin>>ans;
    for(int i=1;i<n;i++){
        cin>>a[i];
        ans=gcd(ans,a.at(i));
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(void) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a < c) {
        if (b > c) {
            cout << "Yes";
        }
        else {
            cout << "No";
        }
    }
    else {
        if (b < c) {
            cout << "Yes";
        }
        else {
            cout << "No";
        }
    }
    return 0;
}

Measured memory_bytes: 256
def main():
    s, t = input().split()
    a, b = map(int, input().split())
    u = input()

    if s == u:
        print(a-1, b)
    elif t == u:
        print(a, b-1)
    else:
        print(a, b)



if __name__ == '__main__':
    main()


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


 int main(){

long long n,sum=0;
cin >> n;

for(int i=1;i<=n;i++)
{
	if(i%3!=0 && i%5!=0)
	{
		sum=sum+i;
	}
}

cout << sum << endl;
 
 
 
 
 return 0;
 }









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

#define int long long

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

int N;
int A[100000], s[100000];

signed main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        s[i] = A[i];
    }
    sort(s, s + N);
    int ans = 0;
    for (int i = 0; i < N; i += 2) {
        if ((lower_bound(s, s + N, A[i]) - s) % 2 == 1) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
k = int(input())

def gcd(a, b):
    if a > b:
        a, b = b, a
    if b % a == 0:
        return a
    else:
        return gcd(b-(b//a)*a, a)

res = 0
for i in range(1, k+1):
    res += i
for i in range(1, k+1):
    for j in range(i+1, k+1):
        tmp = gcd(i, j)
        res += 6*tmp
for i in range(1, k+1):
    for j in range(i+1, k+1):
        for h in range(j+1, k+1):
            tmp = gcd(i, gcd(j, h))
            res += 6*tmp
print(res)

Measured memory_bytes: 9232
from collections import defaultdict
dic = defaultdict(list)
for i in range(3):
    a = list(map(int,input().split()))
    for j in range(3):
        dic[a[j]].append([i,j])
n = int(input())
B = []
for _ in range(n):
    b = int(input())
    B.append(b)
h = [0]*3
w = [0]*3
d = 0
di = 0
for b in B:
    if b not in dic:
        continue
    x,y = dic[b][0]
    if x== y:
        d += 1
    if x + y ==2:
        di += 1
    h[x] += 1
    w[y] += 1
for i in range(3):
    if h[i]==3 or w[i]==3:
        print('Yes');exit()
if d ==3 or di ==3:
    print('Yes');exit()
print('No')


Measured memory_bytes: 64904
#!/user/bin/env python
#pythonプログラムであることを示している

# -*- coding: utf-8 -*-
"""
このプログラムはPythonを書く際のテンプレとなっています。これをコピペしてコーディングを行なってください。
なお字下げしないこと！！
"""

__author_ = 'Maruta Yuzuha'
__version_ = '1.0.0'
__date__ = '2019/12/25'

def main():
    """
    ここでプログラムの解説を行う
     >>main()
    Hello world.
    0
    """
    s = input().split()
    a = list(map(int, input().split()))
    u = input()
    
    if u == s[0]:
        a[0] -= 1
    else:
        a[1] -= 1
    print(str(a[0])+' '+ str(a[1]))
    return 0

if __name__ == '__main__':
    #上記のifの記述によってこのスクリプトファイルが起動された時だけ実行する部分になる。
    #ちなみにスクリプトが "モジュールとして"インポートされた時には実行されない、

    #単体テスト:モジュールのdocstring(ドキュメンテーション文字列)に記載された全ての対話実行例が書かれている通りに動作するかを確認
    #python ファイル名 -v
    import doctest
    doctest.testmod()

    #実際にmain()を呼び出して、結果を得て、その結果でPythonシステムを終える
    import sys
    sys.exit(main())

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

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<double, double> Pdd;
typedef pair<ll, ll> P;

const ll mod = 1e9+7;
const int INF = 2e9;
const double epsilon = 1e-7;
const double PI = 3.1415926535;

ll ma(ll x, ll y){
    if(x>y)return x;
    return y;
}
int main(void){
    int n; cin >>n;
    if(n%2 == 0){
        printf("%d\n", n*(n-2)/2);
        for(int i = 1;i <= n;i++)for(int j = i+1;j <= n;j++)if(i + j != n + 1)printf("%d %d\n", i, j);
    }else{
        printf("%d\n", (n-1)*(n-1)/2);
        for(int i = 1;i <= n;i++)for(int j = i+1;j <= n;j++)if(i + j != n)printf("%d %d\n", i, j);
    }
	return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	static final int P = 1_000_000_007;

	void solve() throws IOException {
		int n = nextInt();
		int k = nextInt();

		if (k == 1) {
			out.println(1);
			return;
		}

		ModuloCombinatorics mc = new ModuloCombinatorics(n * k, P);

		int[][] dp = new int[n + 1][n + 1];
		dp[0][0] = 1;
		for (int i = 0; i <= n; i++) {
			for (int j = i; j <= n; j++) {

				if (i > 0) {
					dp[i][j] += dp[i - 1][j];
					if (dp[i][j] >= P) {
						dp[i][j] -= P;
					}
				}

				if (j > i) {
					dp[i][j] += (int) ((long) dp[i][j - 1]
							* mc.choose(i + j * (k - 1) - 1, k - 2) % P);
					dp[i][j] %= P;
				}

			}
		}

		int ret = (int)((long)dp[n][n] * mc.fact[n] % P);

		out.println(ret);
	}

	static class ModuloCombinatorics {
		/** maximal needed number, N itself is included **/
		final int N;

		/** prime modulo **/
		final int P;

		/** factorials **/
		final int[] fact;

		/** multiplicative inverses, take care to not touch inv[0] **/
		final int[] inv;

		/** inverse factorials **/
		final int[] invFact;

		public ModuloCombinatorics(int N, int P) {
			this.N = N;
			this.P = P;
			fact = new int[N + 1];
			fact[0] = 1;
			for (int i = 1; i <= N; i++) {
				fact[i] = (int) ((long) i * fact[i - 1] % P);
			}

			inv = new int[N + 1];
			inv[1] = 1;
			for (int i = 2; i <= N; i++) {
				inv[i] = P - (int) ((long) (P / i) * inv[P % i] % P);
			}

			invFact = new int[N + 1];
			invFact[0] = 1;
			for (int i = 1; i <= N; i++) {
				invFact[i] = (int) ((long) invFact[i - 1] * inv[i] % P);
			}
		}

		public int choose(int n, int k) {
			if (n < 0 || k < 0 || k > n) {
				return 0;
			}
			return (int) ((long) fact[n] * invFact[k] % P * invFact[n - k] % P);
		}

		/** a^b modulo mod, mod is arbitrary **/
		static public int pow(int a, long b, int mod) {
			if (a < 0 || a >= mod || b < 0) {
				throw new IllegalArgumentException();
			}
			int ret = 1;
			for (; b > 0; b >>= 1) {
				if ((b & 1) == 1) {
					ret = (int) ((long) ret * a % mod);
				}
				a = (int) ((long) a * a % mod);
			}
			return ret;
		}

		/** a^b modulo P **/
		public int pow(int a, long b) {
			return pow(a, b, P);
		}
	}

	Main() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new Main();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}

Measured memory_bytes: 82388
#include <iostream>
#include <algorithm>

using namespace std;
int dp[17][17];
bool stop[17][17];

int solve(int y, int x){

  if (dp[y][x] != 0)
    return dp[y][x];
  if (y == 0 || x == 0)
    return 0;
  if (x == 1 && y == 1)
    return 1;
  if (stop[y][x]){
    return 0;
  }

  dp[y][x] = (solve(y - 1, x) + solve(y, x - 1));
  return dp[y][x];
}

int main() {
  while (true) {
    int x,y,n;
    cin >> x >> y;
    if(x == 0 && y == 0)
      return 0;

    cin >> n;

    fill( dp[0], dp[17], 0);
    fill( stop[0], stop[17], false );

    for (int i = 0; i < n; i++){
      int sx,sy;
      cin >> sx >> sy;
      stop[sy][sx] = true;
    }

   cout << solve(y,x) << endl;
 }
 return 0;
}

Measured memory_bytes: 1160
import math

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

aa = 10*math.ceil(a/10)
bb = 10*math.ceil(b/10)
cc = 10*math.ceil(c/10)
dd = 10*math.ceil(d/10)
ee = 10*math.ceil(e/10)

adif = aa-a
bdif = bb-b
cdif = cc-c
ddif = dd-d
edif = ee-e

ans = aa+bb+cc+dd+ee - max(adif,bdif,cdif,ddif,edif)
print(ans)

Measured memory_bytes: 3064
n, k = gets.to_s.split.map{|t| t.to_i }
a    = gets.to_s.split.map{|t| t.to_i }.sort
f    = gets.to_s.split.map{|t| t.to_i }.sort.reverse

m = []
n.times do |i|
   m << [a[i] * f[i], a[i], f[i]]
end

m.sort_by!{|(af,_, _)| -af }

ans = (0 .. m[0][0]).bsearch do |x|
  
  k_x = 0
  m.each do |(m_i, a_i, f_i)|
    break if m_i <= x
    k_x += ( m_i - x + f_i - 1 ) / f_i
  end
  
  k_x <= k
end

puts ans

Measured memory_bytes: 45624
n,m=map(int,input().split())
a={int(input()) for _ in range(m)}
mod=10**9+7

dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
   dp[1]=1

for i in range(2,n+1):
      if i in a:
            continue
      else:
            dp[i]=dp[i-2]+dp[i-1]
print(dp[-1]%mod)

Measured memory_bytes: 460020
/*
    author: blue_matrix
*/
#include <bits/stdc++.h>
using namespace std;

#define n_l '\n'
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl
#define ll long long
bool comp(pair<ll,ll> a,pair<ll,ll> b)
{
    return a.first>b.first;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll k,a,b;
    cin>>k>>a>>b;
    if(a/k!=b/k)
        cout<<"OK"<<endl;
    else if(a%k==0 || b%k==0)
        cout<<
        "OK"<<endl;
    else
    {
        cout<<"NG"<<endl;
    }
    
    return 0;
}

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

class Node
{
	public:
	vector<int> to,c;
};

class Trl
{
	public:
	int p,c,dc;

	Trl(int p, int c):p(p),c(c){}
	bool operator<(const Trl& t) const
	{
		return c>t.c;
	}
};


int main()
{
	int n,m;
	int a,b,c;
	while(cin >> n >> m , (n||m))
	{
		Node node[100];
		while(m--)
		{
			cin >> a >> b >> c;
			node[a].to.push_back(b);
			node[b].to.push_back(a);
			node[a].c.push_back(c);
			node[b].c.push_back(c);
		}
		
		int total = 0;
		bool visit[100] = {false};
		priority_queue<Trl> q;
		q.push(Trl(0,0));

		while(!q.empty())
		{
			Trl t=q.top(); q.pop();
			if(visit[t.p]) continue;

			visit[t.p] = true;
			total += t.c;

			for(int i=0; i<node[t.p].to.size(); i++)
			{
				int next = node[t.p].to[i];
				int tc   = node[t.p].c[i];
				if(visit[next]) continue;
				
				q.push(Trl(next,tc));
			}
		}

		cout << total << endl;
	}
	return 0;
}

Measured memory_bytes: 0