akhauriyash/Code-Regression huggingface dataset:
import itertools

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

comb = list(itertools.combinations_with_replacement(range(1, M+1), N))
#print(comb)

A = []
for _ in range(Q):
    A.append(tuple(map(int,input().split())))
#print(A)
cnt = 0
ans = 0
for i in comb:
    for k in range(Q):
        a = A[k][0]
        b = A[k][1]
        c = A[k][2]
        d = A[k][3]
        if i[b-1] - i[a-1] == c:
            cnt += d
    ans = max(ans,cnt)
    cnt = 0
print(ans)

Measured memory_bytes: 84448
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
const int MX = 1e5;
int main(){
  int X,N;
  cin >> X >> N;
  vector<int>P(N);
  for (int i=0; i<N; i++) cin >> P[i];
  vector<int>Q(105);
  for (int i=0; i<105; i++){
    Q[i] = i-1;
  }
  sort(P.begin(),P.end());
  vector<int>sa;
  set_difference(Q.begin(), Q.end(), P.begin(), P.end(), back_inserter(sa));  

  int ans = 0;
  int okisa = sa.size();

  int mini = 100000000;
  for (int i=okisa-1; i>-1; i--){
    if ((sa[i]-X)*(sa[i]-X) <= mini){
      mini = (sa[i]-X)*(sa[i]-X);
      ans = sa[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
import itertools

def canMakeTriangle(x,y,z):
    if x == y or x == z or y == z:
        return False
    elif x+y>z and y+z>x and z+x>y:
        return True
    else:
        return False


def resolve():
    _ = int(input())
    L = list(map(int, input().split()))
    cnt = 0
    for l in itertools.combinations(L,3):
        if canMakeTriangle(l[0], l[1], l[2]):
           cnt += 1

    print(cnt) 
    
resolve()

Measured memory_bytes: 67828
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <cctype>
#include <cassert>

using namespace std;

#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,b,e) for(int i = (b); i <= (e); i++)
#define INF (1001001001)
#define EPS (1e-15)

#define pr(x) do{cout << (#x) << " = " << (x) << endl;}while(0)
#define pri(x,i) do{cout << (#x) << "[" << i << "] = " << (x[i]) << endl;}while(0)
#define pra(x,n) rep(__i,n) pri(x,__i);
#define prar(x,b,e) repr(__i,b,e) pri(x,__i);

typedef long long ll;
typedef pair<int, int> pint;
typedef vector<int> vint;

ll MOD = 1000000007;

int in() {
	int a;
	scanf("%d ", &a);
	return a;
}

ll f[100010];
ll fac(int n) {
	return f[n];
}

int main() {
	f[0] = 1;
	for (int i = 1; i < 100008; i++) f[i] = f[i-1] * i % MOD;
	int N = in();
	int M = in();
	int sa = abs(N - M);
	if (sa >= 2) {
		cout << 0 << endl;
		return 0;
	}
	
	if (N == M) {
		ll ans = fac(N);
		ans = ans * ans % MOD;
		cout << (2 * ans % MOD) << endl;
	}
	else {
		ll ans = fac(N);
		ans = ans * fac(M) % MOD;
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
string S[2];
int Q;
int a[2][100100];
int b[2][100100];
int main(){
	cin >> S[0];
	cin >> S[1];
	for(int i=0;i<2;i++){
		for(int j=0;j<S[i].size();j++){
			if(S[i][j]=='A')a[i][j+1]=1;
			else b[i][j+1]=1;
		}
		for(int j=0;j<S[i].size();j++){
			a[i][j+1]+=a[i][j];
			b[i][j+1]+=b[i][j];
		}
	}
	cin >> Q;
	for(int i=0;i<Q;i++){
		int A,B,C,D;
		cin >> A >> B >> C >> D;
		int k = a[0][B]-a[0][A-1]+2*(b[0][B]-b[0][A-1]);
		int l = a[1][D]-a[1][C-1]+2*(b[1][D]-b[1][C-1]);
		if(k%3==l%3)cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 2432
#include<iostream>
#include<string>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
using namespace std;

int main() {
  int A, B;
  cin >> A >> B;

  char c; string ans = "Yes";
  rep(i,0,A+B) {
    cin >> c;
    if (i == A) {
      if (c != '-') ans = "No";
    }
    else {
      int n = c - 48;
      if (n < 0 || 9 < n) ans = "No";
    }
  }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

int main(void){
	ll n;
	cin >> n;
	string s;
	while(n){
		if (n % 26 == 0){
			s += 'z';
			n--;
		}else s += n % 26 + 'a' - 1;
		n /= 26;
	}
	reverse(all(s));
	co(s);

	return 0;
}


Measured memory_bytes: 3584
#include <iostream>
    #include <math.h>
    using namespace std;
     
    int main() {
    int a,b,c,d;
    cin >> a;
    for(int i=0 ; i<a ; i++){
    cin >>b>>c>>d;
    if(b*b + c*c == d*d || c*c+d*d==b*b || b*b+d*d==c*c){
    cout << "YES"<<endl;
    }
    else{
    cout << "NO"<<endl;
    }
    }
    return 0;
    }

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define so sizeof
#define pb push_back
#define vl vector<ll>
#define el endl;cout.flush()
#define be begin()
#define fi first
#define se second
#define br break
#define sz size()
#define en end()
#define ro return 0
#define br break
#define con continue;
#define um unordered_map<ll,ll>
#define ms(x) memset(x , 0 , so x)
#define all(x) (x).be , (x).en
#define rall(x) (x).rbegin() , (x).rend()
#define acc(x) accumulate((x).be , (x).en , 0)
#define forn(i,a,b) for(ll i=a;i<=b;++i)
#define forr(i,a,b) for(ll i=a;i<b;++i)
#define rng_58 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define plll pair<ll,pair<ll,ll>>
#define plvl pair<pair<ll,ll> ,ll>
#define mp make_pair
int main()
{
    ios;
    ll n , x;
   // freopen("in.txt" , "r" , stdin);
    cin >> n >> x;
    vl v;
    forn(i , 1 , n ){
       ll y;
       cin >>  y;
       v.pb(y);
    }
    ll ans[n+2];
    ms(ans);
    forn(i ,  1 , n ) {
       ans[i-1] = v[i-1];
    }
    ll tot = 3e18;
    forn(k, 0 , n-1){
        ll cost = k * x ;
        forn(i , 0 , n-1 ){
           ans[i] = min(ans[i] , v[(i - k + n) %n]);
        }
        forn(i , 0, n -1){
           cost = cost + ans[i];
        }
        tot = min(tot , cost) ;
    }
    cout << tot << el ;
    ro ;
}

























Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import javax.swing.InputMap;

public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s[] = br.readLine().split(" ");
		int W = Integer.parseInt(s[0]);
		int H = Integer.parseInt(s[1]);
		int x = Integer.parseInt(s[2]);
		int y = Integer.parseInt(s[3]);
		int r = Integer.parseInt(s[4]);
		if(x >= r && y >= r && W-x >= r && H-y >= r){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	
	}

}

Measured memory_bytes: 24452
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0
for a in range(A+1):
    for b in range(B+1):
        c = X//50-10*a-2*b
        if 0 <= c and c <= C:
            ans += 1

print(ans)


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

int main()
{
    int a;
    string s, t;
    cin >> s >> t;
    a = stoi(s + t);
    string ans = "No";

    rep(i, 1000)
    {
        if (i * i == a)
            ans = "Yes";
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
import fractions

a,b,c,d = map(int,input().split()) 

cd = (c * d) // fractions.gcd(c, d)
b_c = b // c
b_d = b // d
b_cd = b // cd
a_c = a // c
a_d = a // d
a_cd = a // cd

ans = b - b_c - b_d + b_cd - a + a_c + a_d - a_cd

if a % c != 0 and a % d!= 0:
    ans += 1

print(ans)

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

#define lli long long int
int main(void)
{
	lli w, h, x, y;
	scanf("%lld %lld %lld %lld",&w,&h,&x,&y);
	double half;
	half = (double)(w*h) / 2.0;
	int is_center = 0;
	if ((2*x == w) && (2*y == h))
		is_center = 1;
	printf("%.10lf %d\n", half, is_center);
	return(0);
}


Measured memory_bytes: 128
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
step_patern = [0,1]
for i in range(n):
         step_patern.append(step_patern[i] + step_patern[i+1])
kankaku = []
tmp = 0
for i in range(len(a)):
         kankaku.append(a[i] - tmp)
         tmp = a[i] +1
kankaku.append(n + 1 - tmp)
ans = 1
for i in kankaku:
         ans *= step_patern[i]
         ans %= (10 ** 9) +7
print(ans)


Measured memory_bytes: 464936
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int zero = 1500;

int main(){
  int n, a;
  cin >> n >> a;
  vector<int> an(n);
  for(int i=0; i<n; ++i) cin >> an[i];
  vector<vector<ll>> dp(n,vector<ll>(3000,0));
  dp[0][zero] = 1;
  for(int i=0; i<n; ++i){
    if(i == 0){
      dp[i][zero +an[i] -a] += 1;
      continue;
    }
    for(int j=0; j<3000; ++j){
      dp[i][j] = dp[i-1][j];
      if(j-(an[i]-a) >= 0 && j-(an[i]-a) < 3000){
        dp[i][j] += dp[i-1][j-(an[i]-a)];
      }
    }
  }
  /*
  for(int i=0; i<n; ++i){
    for(int j=zero-10; j<zero+10; ++j){
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  */
  cout << dp[n-1][zero] -1 << endl;
}

Measured memory_bytes: 4528
import numpy as np

if __name__ == '__main__':
    x, y = map(int, input().split())
    res = 1000000000000
    ax, ay = (abs(x), abs(y))
    if x <= y:
        res = min(res, y-x)
    if x * y <= 0:
        res = min(res, abs(ax-ay)+1)
    else:
        res = min(res, abs(ax-ay)+2)
    print(res)



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

typedef long long ll;
const int N = 100005;
const int M = 1000000007;

ll n, s;

ll f(ll b, ll n) {
  if (b <= 1) { return -1; }
  if (n < b) { return n; }
  return f(b, n / b) + n % b;
}

ll factor[N], facCnt;
void getFactors(ll x) {
  facCnt = 0;
  for (ll i = 1; i * i <= x; i++) {
    if (x % i == 0) {
      factor[facCnt++] = i;
      if (x / i != i) { factor[facCnt++] = x / i; }
    }
  }
  sort(factor, factor + facCnt);
}

int main() {
  while (~scanf("%lld%lld", &n, &s)) {
    if (s > n) { puts("-1"); continue; }
    if (s == n) { printf("%lld\n", n + 1); continue; }
    ll ans = -1;
    for (ll b = 2; b * b <= n && ans == -1; b++) {
      if (f(b, n) == s) { ans = b; }
    }
    getFactors(n - s);
    for (int i = 0; i < facCnt && ans == -1; i++) {
      if (f(factor[i] + 1, n) == s) { ans = factor[i] + 1; }
    }
    printf("%lld\n", ans);
  }
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int dice[6];
    int i,temp;
    char ins[101];
    for(i=0;i<6;i++) scanf("%d",&dice[i]);
    scanf("%s",ins);
    for(i=0;i<strlen(ins);i++){
        if(ins[i]=='N'){
            temp=dice[0];
            dice[0]=dice[1];
            dice[1]=dice[5];
            dice[5]=dice[4];
            dice[4]=temp;
        }else if(ins[i]=='E'){
            temp=dice[0];
            dice[0]=dice[3];
            dice[3]=dice[5];
            dice[5]=dice[2];
            dice[2]=temp;
        }else if(ins[i]=='S'){
            temp=dice[0];
            dice[0]=dice[4];
            dice[4]=dice[5];
            dice[5]=dice[1];
            dice[1]=temp;
        }else if(ins[i]=='W'){
            temp=dice[0];
            dice[0]=dice[2];
            dice[2]=dice[5];
            dice[5]=dice[3];
            dice[3]=temp;
        }
    }

    printf("%d\n",dice[0]);
    return 0;
}



Measured memory_bytes: 2132
A=input()
B=input()
C=input()
cnta=1
cntb=1
cntc=1
pos='a'
for i in range(len(A)+len(B)+len(C)):
    if pos=='a' and cnta==len(A)+1:
        print('A')
        break
    if pos=='b' and cntb==len(B)+1:
        print('B')
        break
    if pos=='c' and cntc==len(C)+1:
        print('C')
        break
    if pos=='a':
        pos=A[cnta-1]
        cnta+=1
    elif pos=='b':
        pos=B[cntb-1]
        cntb+=1
    else:
        pos=C[cntc-1]
        cntc+=1

Measured memory_bytes: 3064
///*Bismillahir Rahmanir Rahim***///
/***Stay_Home_Stay_Safe***/
///**Author Thasin Sheikh**///
/*while(a)
    {
        if(a%2==0)
            dvi.push_back(0);
        else
            dvi.push_back(1);
        a/=2;
    }
    reverse(dvi.begin(),dvi.end());*/
#include<bits/stdc++.h>
using namespace std;
#define MAX 35000
#define makefast__  ios_base::sync_with_stdio(false);
using ll=long long int  ;
using dl =double;
const int N = 2e5 + 10;
ll aarray[200000+10];
ll magic[101][101];
vector<ll>primes;
bool prime[1000001];
int main()
{
    makefast__
    string str;
    ll a,b,c,d,e,f,x,y,k,t,A=0,B=0,L,j,i,l,r,m,n,C=0,ans=0,sum=0,sum1=0;
    vector<ll>v,v1;
    queue<ll>qu;
    cin>>str;
    for(i=0;i<str.length()-1;i++)
    {
        if(str[i]==str[i+1])
        {
            cout<<"Bad"<<endl;
            return 0;
        }
    }
    cout<<"Good"<<endl;

    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7;

int main() {
  int N;
  cin >> N;
  int i=N%10;
  if(i==2||i==4||i==5||i==7||i==9)
    cout << "hon" << endl;
  else if(i==0||i==1||i==6||i==8)
    cout << "pon" << endl;
  else
    cout << "bon" << endl;
}

Measured memory_bytes: 3624
import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
	Scanner scan = new Scanner(System.in);
	
	int N;   //整数の個数
	N = scan.nextInt();

	long max1 = 0;
	long max2 = 0;
	long sum = 0;

	int[] A = new int[N];   //整数
	for(int i = 0; i < N; i++){
	    A[i] = scan.nextInt();
	}

	//昇順ソート
	Arrays.sort(A);

	//整数が偶数個の場合
	if(A.length % 2 == 0){
	    for(int i = 0; i < (N/2) ; i++){
		if(i == (N/2-1)){
		    sum -= A[i];
		}else{
		    sum -= (A[i]*2);
		}
	    }
	    for(int i = (N/2); i < N; i++){
		if(i == (N/2)){
		    sum += A[i];
		}else{
		    sum += (A[i]*2);
		}
	    }
	}

	//整数が奇数個の場合
	if(A.length % 2 != 0){
	    //M字型
	    for(int i = 0; i <= (N/2); i++){
		if(i == (N/2-1) || i == (N/2)){
		    max1 -= A[i];
		}else{
		    max1 -= (A[i]*2);
		}
	    }
	    for(int i = (N/2+1); i < N; i++){
		max1 += (A[i]*2);
	    }
	    
	    //W字型
	    for(int i = 0; i < (N/2); i++){
		max2 -= (A[i]*2);
	    }
	    for(int i = (N/2); i < N; i++){
		if(i == (N/2) || i == (N/2+1)){
		    max2 += A[i];
		}else{
		    max2 += (A[i] * 2);
		}
	    }

	    //大きい方を評価
	    sum = Math.max(max1, max2);
	}

	System.out.println(sum);
    }
}


Measured memory_bytes: 53084
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  int n;cin>>n;
  vector<int> a(n+1,0);
  rep(i,n)cin>>a[i];
  int money=1000;
  int kabu=0;
  bool kau=true;
  lint res=0;
  rep(i,n){
    if(kau){
      if(a[i+1]>a[i]){
        kabu+=money/a[i];
        money%=a[i];
        kau=false;
      }
    }
    else{
      if(a[i+1]<a[i]){
        kau=true;
        money+=kabu*a[i];
        kabu=0;
      }
    }
    res=max(res,money);
  }
  cout<<res<<"\n";
  return 0;
}


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

int main() {
	int n;
  	cin >> n;
  	int a[n], sum = 0;
  	for(int i = 0; i < n; ++i) {
      
      cin >> a[i];
      sum += a[i];
    }
  	int p= *max_element(a, a + n);
  	sum -= p;
  	if(sum > p)
      cout << "Yes";
  	else cout << "No";
}

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

int main() {
	char c; cin >> c;
	switch (c) {
	case 'a':case 'e':case 'i':case 'o':case 'u':puts("vowel"); break;
	default:puts("consonant"); break;
	}
}

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

int main() {
  int n;
  char str[10], com[13];
  map<string, bool>  T;

  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    scanf("%s%s", com, str);
    if ( com[0] == 'i' ) T[string(str)] = true;
    else {
      if ( T[string(str)] ) printf("yes\n");
      else printf("no\n");
    }
  }

  return 0;
}


Measured memory_bytes: 47560
#line 1 "/workspaces/compro/lib/template.hpp"


#line 1 "/workspaces/compro/lib/io/vector.hpp"
#include <iostream>
#include <vector>

#ifndef IO_VECTOR
#define IO_VECTOR

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

template <class T> std::istream &operator>>(std::istream &in, std::vector<T> &v) {
  for (auto &el : v) {
    std::cin >> el;
  }
  return in;
}

#endif
#line 4 "/workspaces/compro/lib/template.hpp"
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }

void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}

// C++ 17に完全移行したら消す
// 最大公約数を求める
template <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }

// 最小公倍数を求める
template <class T> T lcm(T n, T m) {
  int g = gcd(n, m);
  return n * m / g;
}

// 重複を消す。計算量はO(NlogN)
template <class T> void unique(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}


#line 2 "main.cpp"

long long solve(long long N, long long X, long long T) {
  int ans = 0;
  int co = 0;
  while (co < N) {
    ans += T;
    co += X;
  }
  return ans;
}

// generated by online-judge-template-generator v4.4.0 (https://github.com/kmyk/online-judge-template-generator)
int main() {
  long long N, X, T;
  std::cin >> N >> X >> T;
  auto ans = solve(N, X, T);
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 3632
package main

import (
	"fmt"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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

	left := make([]int, n)
	left[0] = 0
	for i := 1; i < n; i++ {
		left[i] = left[i-1]
		if s[i-1] == 'W' {
			left[i]++
		}
	}

	right := make([]int, n)
	right[n-1] = 0
	for i := n - 2; i >= 0; i-- {
		right[i] = right[i+1]
		if s[i+1] == 'E' {
			right[i]++
		}
	}

	ans := n
	for i := 0; i < n; i++ {
		ans = min(ans, left[i]+right[i])
	}
	fmt.Println(ans)
}


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


namespace ALDS1_2_B_Selection_Sort
{
	class Program
	{
		static void Main ( string[] args )
		{
			int numCount = int.Parse (Console.ReadLine ().Trim ());
			int[] numArray = Console.ReadLine ().Trim ().Split (' ').Select (x => int.Parse (x)).ToArray ();

			int swapCount = 0;

			for (int index = 0; index < numCount; index++)
			{
				int minIndex = index;

				for (int index2 = index; index2 < numCount; index2++)
				{
					if (numArray[index2] < numArray[minIndex])
					{
						minIndex = index2;
					}
				}

				if (index != minIndex)
				{
					var tmp = numArray[index];
					numArray[index] = numArray[minIndex];
					numArray[minIndex] = tmp;

					swapCount++;
				}
			}

			for (int lp = 0; lp < numArray.Length - 1; lp++)
			{
				Console.Write (numArray[lp] + " ");
			}
			Console.WriteLine (numArray[numArray.Length - 1]);

			Console.WriteLine (swapCount);

		}
	}
}

Measured memory_bytes: 9484
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const int INF = 1001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

vector<int> factorization(int num)
{
    map<int, int> mp;

    int tmp = num;
    for (int i = 2; i * i <= num; i++)
    {
        while (tmp % i == 0)
        {
            mp[i]++;
            tmp /= i;
        }
    }
    if (tmp != 1)
    {
        mp[num]++;
    }
    vector<int> ret;
    for (auto m : mp)
    {
        ret.push_back(m.first);
    }
    return ret;
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    map<int, int> mp;
    for (int i = 0; i < n; i++)
    {
        mp[a[i]]++;
    }
    vector<int> nums;
    for (auto m : mp)
    {
        if (m.second == 1)
        {
            nums.push_back(m.first);
        }
        else
        {
            nums.push_back(m.first);
            nums.push_back(m.first);
        }
    }
    int dp[1000010];
    memset(dp, 0, sizeof(dp));
    for (int num : nums)
    {
        int number = num;
        do
        {
            dp[number]++;
            number += num;
        } while (number <= 1000000);
    }
    int ans = 0;
    for (int num : nums)
    {
        if (dp[num] == 1)
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


Measured memory_bytes: 18156
N = int(input())
A = list(map(int,input().split()))

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*(M+1)

n=M
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

for i in primes:
    for j in range(i,M+1,i):
        if num_list[j]==1:
            pairwise[i] += 1
        
ans = 0    
for i in pairwise:
    if i>1:
        ans += 1
        break
    
if setwise == 1 and ans == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")



Measured memory_bytes: 410772
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

int main()
{
  ll X, Y; cin >> X >> Y;
  if (X%Y == 0) {
    cout << -1 << endl;
  } else {
    cout << X << endl;
  }
}

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

int main()
{   
    int n;
    int cx,cy,ch;
    cin>>n;
    int x[n],y[n],h[n];
    for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>h[i];
    
    for(int i=0;i<n;i++){
        if(h[i]>0){
            for(cx=0;cx<=100;cx++){
                for(cy=0;cy<=100;cy++){
                    ch=h[i]+abs(cx-x[i])+abs(cy-y[i]);
                    int flg=1;
                    for(int j=0;j<n;j++){
                        if(j==i){}
                        else if(max(ch-abs(cx-x[j])-abs(cy-y[j]),0)!=h[j]) flg=0;
                    }
                    if(flg==1){
                        cout<<cx<<' '<<cy<<' '<<ch<<endl;
                        return 0;
                    }
                }
            }
        }
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
inline ll read(){
	ll re=0,flag=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-') flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
	return re*flag;
}
ll n,K,cnt,a[100010],b[100010],tmp[400010],seg[400010],L[100010],R[100010],dp[100010],sum[100010];
void push(ll num){
	if(!seg[num]) return;
	seg[num<<1]=seg[num<<1|1]=seg[num];
	seg[num]=0;
}
void change(ll l,ll r,ll ql,ll qr,ll num,ll val){
//	cout<<"	change "<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<num<<' '<<val<<'\n';
	if(ql>qr) return;
	if(l>=ql&&r<=qr){seg[num]=val;return;}
	push(num);
	ll mid=(l+r)>>1;
	if(mid>=ql) change(l,mid,ql,qr,num<<1,val);
	if(mid<qr) change(mid+1,r,ql,qr,num<<1|1,val);
}
ll query(ll l,ll r,ll num,ll pos){
//	cout<<"	query "<<l<<' '<<r<<' '<<num<<' '<<pos<<' '<<seg[num]<<'\n';
	if(l==r) return seg[num];
	push(num);
	ll mid=(l+r)>>1;
	if(mid>=pos) return query(l,mid,num<<1,pos);
	else return query(mid+1,r,num<<1|1,pos);
}
ll ask(ll pos){
	ll choose=query(1,cnt,1,pos);
//	cout<<"	**** ask "<<pos<<' '<<choose<<'\n';
	if(!choose) return 0;
	return (dp[choose]+(tmp[L[choose]]-tmp[pos]+K)%K);
}
int main(){
	n=read();K=read();ll i;
	for(i=1;i<=n;i++) {
		a[i]=read();b[i]=read();
		sum[i]=(sum[i-1]+a[i]);
//		cout<<"input "<<i<<' '<<a[i]<<' '<<sum[i]<<'\n';
		if(b[i]==2) continue;
		if(2*a[i]>K){
			puts("-1");return 0;
		}
	}
//	cout<<"first input finish\n";
	for(i=n;i>=1;i--){
		if(b[i]==1){
			L[i]=(-2ll*sum[i-1]%K+K)%K;
			R[i]=(-2ll*sum[i]%K+K)%K;
		}
		else L[i]=0,R[i]=K-1;
		tmp[++cnt]=L[i],tmp[++cnt]=R[i];
	}
//	cout<<"second input finish\n";
	sort(tmp+1,tmp+cnt+1);
	cnt=unique(tmp+1,tmp+cnt+1)-tmp-1;
	for(i=n;i>=1;i--){
		L[i]=lower_bound(tmp+1,tmp+cnt+1,L[i])-tmp;
		R[i]=lower_bound(tmp+1,tmp+cnt+1,R[i])-tmp;
		dp[i]=ask(L[i]);
//		cout<<"get dp "<<dp[i]<<' '<<L[i]<<' '<<tmp[L[i]]<<' '<<R[i]<<' '<<tmp[R[i]]<<'\n';
		if(L[i]>R[i]) change(1,cnt,R[i]+1,L[i]-1,1,i);
		else change(1,cnt,1,L[i]-1,1,i),change(1,cnt,R[i]+1,cnt,1,i);
	}
	ll ans=dp[1];
	for(i=cnt;i>=1;i--) ans=min(ans,ask(i));
	printf("%lld\n",ans+sum[n]*2ll);
//	cout<<"double check "<<ans<<' '<<sum[n]*2ll<<'\n';
}

Measured memory_bytes: 11136
import sys

sys.setrecursionlimit(1000000)



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

    has_set = set()
    a_dic = {}
    for i in range(k):
        input()
        for z in list(map(int, input().split())):
            has_set.add(z)

    print(n-len(has_set))




main()


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

const int MAX_V = 50;
const int MAX_S = MAX_V*50+5;
const ll INF = 1e18;

struct Edge {
  int to, a, b;
  Edge(int to, int a, int b):to(to),a(a),b(b) {}
};

struct Data {
  int v, s;
  ll x;
  Data(int v, int s, ll x):v(v),s(s),x(x) {}
  bool operator<(const Data& a) const {
    return x > a.x;
  }
};

vector<Edge> g[MAX_V];
ll dist[MAX_V][MAX_S+5];

int main() {
  int n, m, s;
  cin >> n >> m >> s;
  rep(i,m) {
    int u,v,a,b;
    cin >> u >> v >> a >> b;
    --u; --v;
    g[u].emplace_back(v,a,b);
    g[v].emplace_back(u,a,b);
  }
  rep(i,n)rep(j,MAX_S+5) dist[i][j] = INF;
  s = min(s, MAX_S);
  priority_queue<Data> q;
  auto push = [&](int v, int s, ll x) {
    if (s < 0) return;
    if (dist[v][s] <= x) return;
    dist[v][s] = x;
    q.emplace(v,s,x);
  };
  vector<int> c(n), d(n);
  rep(i,n) cin >> c[i] >> d[i];
  push(0,s,0);
  while (!q.empty()) {
    Data hoge = q.top(); q.pop();
    int v = hoge.v, s = hoge.s;
    ll x = hoge.x;
    if (dist[v][s] != x) continue;
    {
      int ns = min(s+c[v], MAX_S);
      push(v,ns,x+d[v]);
    }
    for (Edge e : g[v]) {
      push(e.to, s-e.a, x+e.b);
    }
  }
  for (int i = 1; i < n; ++i) {
    ll ans = INF;
    rep(j,MAX_S+5) {
      ans = min(ans, dist[i][j]);
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 6304
# include <bits/stdc++.h>
using namespace std;
const int N = (1 << 13) + 1 , M = 3e3 + 10 , INF = 1e9 + 7;
int dp[M][N];
int main(){
	int n , m;
	cin >> n >> m;
	for(int i = 0; i <= m; i ++)
		for(int j = 1; j < (1 << n); j ++)
			dp[i][j] = INF;
	for(int i = 1; i <= m; i ++){
		int cost , raod , key , bin = 0;
		cin >> cost >> raod;
		for(int j = 0; j < raod; j ++)
			cin >> key,
			bin |= (1 << key - 1);
		for(int j = 0; j < (1 << n); j ++) dp[i][j] = dp[i - 1][j];
		for(int j = 0; j < (1 << n); j ++){
			int cur_bin = j | bin;
			dp[i][cur_bin] = min(dp[i][cur_bin] , dp[i - 1][j] + cost);
		}
	}
	if(dp[m][(1 << n) - 1] == INF) cout << "-1\n";
	else cout << dp[m][(1 << n) - 1] << "\n";
}

Measured memory_bytes: 32256
// 26/01/20 // 12:19 PM //

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long

const int MAXN = (int)(3e3) + 10;

int n, a[MAXN];
int memo[MAXN][MAXN];

int32_t main(){
    fastio;

    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];

    for(int l=n; l>=1; l--){
        for(int r=l; r<=n; r++){
            if(((r-l+1)&1)==(n&1)) // taro
                memo[l][r] = max(a[l] + memo[l+1][r], a[r] + memo[l][r-1]);
            else
                memo[l][r] = min(memo[l+1][r] - a[l], memo[l][r-1] - a[r]);
        }
    }

    cout << memo[1][n] << endl;

    return 0;
}



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

int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(a*b%2&&(c+d)%2){
		cout<<"No"<<endl;
	}
	else{
		cout<<"Yes"<<endl;
	}
}



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

using namespace std;


void solve() {
    int n; cin >> n;
    vector<vector<int>> g(n);
    for (int _ = 1; _ < n; _++) {
        int x,y;
        cin >> x >> y;
        x--;y--;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    vector<int> pa(n,-1);
    vector<int> sz(n, 1);
    function<void(int,int)> dfs = [&](int u, int p){
        for (int v: g[u])if(v!=p){
            pa[v] = u;
            dfs(v,u);
            sz[u] += sz[v];
        }
    };
    dfs(0, -1);
    int d = 0, x = n-1;
    while (x != 0) {
        x = pa[x];
        d++;
    }
    d = (d-1)/2;
    x = n-1;
    while (d--) {
        x = pa[x];
    }

    int b = sz[x], a = n - b;
    cout << (a>b?"Fennec":"Snuke");
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 15872
N = int(input())
A = list(map(int, input().split()))
m =  10**18 
ans = 1
A.sort()
for i in range(N):
  ans *= A[i]
  if ans > m:
    print(-1)
    exit(0)
  if ans == 0:
    break;
#
print(ans)
#

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

typedef long long ll;
typedef vector<ll> V;
typedef pair<ll,ll> P;
typedef map<ll,ll> M;

#define REP(i, n) for(ll (i) = 0; (i) < (n); ++(i))
#define FOR(i, j, n) for(ll (i) = (j); (i) < (n); ++(i))
#define REPR(i, n) for(ll (i) = (n); (i) >= 0; --(i))

V scc(vector<V> edges){
    int n = edges.size();
    vector<V> rev(n);
    REP(i,n)for(auto&xx : edges[i])rev[xx].push_back(i);
    V dfs_num(n, -1);
    V flag(n, 0);
    ll num = 0;
    function<void(ll)> dfs = [&](ll pos){
        flag[pos] = 1;
        for(auto& xx : edges[pos])
            if(!flag[xx])
                dfs(xx);
        dfs_num[pos] = num++;
    };
    REP(i,n){
        if(!flag[i])
            dfs(i);
    }
    V dfs_inv(n);
    REP(i,n){
        dfs_inv[n - 1 - dfs_num[i]] = i;
    }
    num = 0;
    V scc_vec(n, -1);
    function<void(ll)> rdfs = [&](ll pos){
        scc_vec[pos] = num;
        for(auto t : rev[pos])
            if(scc_vec[t] == -1)
                rdfs(t);
    };
    REP(i,n){
        if(scc_vec[dfs_inv[i]] == -1){
            rdfs(dfs_inv[i]);
            ++num;
        }
    }
    return scc_vec;
}

signed main(){
    int n;
    cin >> n;
    V u(n);
    V type(n);
    V d(n);
    vector<V> edges(201);
    REP(i,n){
        string s;
        cin >> u[i] >> s >> d[i];
        d[i] += 100;
        type[i] = (s == "wait");
        if(type[i])
            edges[u[i]].push_back(d[i]);
        else
            edges[d[i]].push_back(u[i]);
    }
    M m;
    auto hog = scc(edges);
    REP(i,edges.size()){
        if(m[hog[i]]++){
            cout << 1 << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}



Measured memory_bytes: 3264
/*   ꧁༒☬महाकाल☬༒꧂ ꧁༒ঔमहाकालঔ༒꧂
                   
                   ঔৣ۝महाकालᴳᵒᵈ۝ঔৣ            
 
 */ 
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T, typename cmp=less<T>> using oset =tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long 
#define mod 1000000007
#define inf 100000000000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _it iterator
#define all(_x) _x.begin(),_x.end()
#define f first
#define s second
#define pb push_back
void mahakal(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
	#endif
}
int main(){
	//mahakal(),fast;
	ll n ,a , b ;
	cin>> n >> a >> b ;
	ll ans = ceil(a/(float)n)*n;
	if(ans>=a && ans<=b)cout<<"OK"<<endl;
	else cout<<"NG"<<endl;
	// cerr<<ans<<endl;

	return 0;
}

Measured memory_bytes: 3608
fun main(args: Array<String>) {
    agc016a()
}

fun agc016a() {
    val s = readLine()!!

    val answer = s.toCharArray().distinct().map { char ->
        var curr = s.toCharArray()
        var cnt = 0
        while (curr.any { it != char }) {
            curr = curr.dropLast(1)
                .mapIndexed { index, c -> if (curr[index + 1] == char) char else c }.toCharArray()
            cnt++
        }
        cnt
    }.min()

    println(answer)
}


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

int main() {
    int A,B,M;
    cin >> A >> B >> M;
    int Aline[A],Bline[B];
    
    
    
    for (int i =0 ;i < A; i++) {
        cin >> Aline[i];
    }
    for (int i =0 ;i < B; i++) {
         cin >> Bline[i];
    }
    int minA=Aline[0];
    int minB=Bline[0];
    for (int i =0 ;i < A; i++) {
        if (minA>Aline[i]){
            minA=Aline[i];
        }
    }
    for (int i =0 ;i < B; i++) {
        if (minB>Bline[i]){
            minB=Bline[i];
         }
    }
    int ans = minA+minB;
    for (int i =0 ;i < M; i++) {
        int AN,BN,CN;
         cin >> AN ;
         cin >> BN ;
         cin >> CN ;
        int tmpAns = Aline[AN-1]+Bline[BN-1]-CN;
        if (ans> tmpAns){
            ans = tmpAns;
        }
    }
    cout<<ans<<endl;
    
    
    
       
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <queue>
#include <complex>
using namespace std;
typedef complex<int> P;

int main()
{
  int W, H;
  while (cin >> W >> H && W != 0) {
    vector<string> roomL(H), roomR(H);
    P startL, startR;
    for (int i = 0; i < H; i++) {
      cin >> roomL[i] >> roomR[i];
      for (int j = 0; j < W; j++) {
        if (roomL[i][j] == 'L') {
          roomL[i][j] = '.';
          startL = P(i, j);
        }
        if (roomR[i][j] == 'R') {
          roomR[i][j] = '.';
          startR = P(i, j);
        }
      }
    }

    queue<pair<P,P> > q;
    q.push(make_pair(startL, startR));
    vector<vector<bool> > visited(W*H, vector<bool>(W*H, false));
    visited[startL.real()*W + startL.imag()][startR.real()*W + startR.imag()] = true;
    while (!q.empty()) {
      const pair<P, P> p = q.front();
      q.pop();
      if (roomL[p.first.real()][p.first.imag()] == '%'
          || roomR[p.second.real()][p.second.imag()] == '%') {
        if (roomL[p.first.real()][p.first.imag()] == '%'
            && roomR[p.second.real()][p.second.imag()] == '%') {
          cout << "Yes" << endl;
          goto NEXT;
        } else {
          continue;
        }
      }

      for (int d = 0; d < 4; d++) {
        static const P dir[] = {P(-1,0), P(1,0), P(0,-1), P(0,1)};
        P nextL = p.first + dir[d];
        P nextR = p.second + P(dir[d].real(), dir[d].imag() == -1 ? 1 : (dir[d].imag() == 1 ? -1 : 0));
        if (nextL.real() == -1 || nextL.real() == H
            || nextL.imag() == -1 || nextL.imag() == W
            || roomL[nextL.real()][nextL.imag()] == '#') {
          nextL = p.first;
        }
        if (nextR.real() == -1 || nextR.real() == H
            || nextR.imag() == -1 || nextR.imag() == W
            || roomR[nextR.real()][nextR.imag()] == '#') {
          nextR = p.second;
        }
        if (!visited[nextL.real()*W + nextL.imag()][nextR.real()*W + nextR.imag()]) {
          q.push(make_pair(nextL, nextR));
          visited[nextL.real()*W + nextL.imag()][nextR.real()*W + nextR.imag()] = true;
        }
      }
    }
    cout << "No" << endl;
NEXT:
    ;
  }
  return 0;
}

Measured memory_bytes: 2588
import scala.io.StdIn.readInt

case class Point(x: Double, y: Double)

object Main extends App {

  val n = readInt()

  val ps = solve(n, Point(0, 0), Point(100, 0))

  val results = ps.map {
    case Point(x, y) => f"$x%.8f $y%.8f"
  }

  results.foreach(println)

  def solve(n: Int, start: Point, end: Point): Iterator[Point] = {
    val th  = math.Pi / 3.0
    val cos = math.cos(th)
    val sin = math.sin(th)

    def koch(depth: Int, p1: Point, p2: Point, zs: List[Point]): List[Point] = {
      if (depth <= 0) zs
      else {
        val s = Point((2.0 * p1.x + p2.x) / 3.0, (2.0 * p1.y + p2.y) / 3.0)
        val t = Point((p1.x + 2.0 * p2.x) / 3.0, (p1.y + 2.0 * p2.y) / 3.0)
        val u = Point(
          (t.x - s.x) * cos - (t.y - s.y) * sin + s.x,
          (t.x - s.x) * sin + (t.y - s.y) * cos + s.y
        )

        val d     = depth - 1
        val list1 = s :: koch(d, p1, s, zs)
        val list2 = u :: koch(d, s, u, list1)
        val list3 = t :: koch(d, u, t, list2)
        koch(d, t, p2, list3)
      }
    }

    val xs = end :: koch(n, start, end, List(start))
    xs.reverseIterator
  }
}



Measured memory_bytes: 57024
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
//////////////////////////////////////////////////////////////////////////////////////////////////////////

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<MOD>;

struct ModCombination {
    vector<mint> Fac;
    vector<mint> Facinv;

    ModCombination(int x) {
        Fac.resize(x+1);
        Facinv.resize(x+1);
        Fac[0] = 1;
        for (long long i = 1; i <= x; i++) Fac[i] = Fac[i-1]*i;
        Facinv[x] = Fac[0]/Fac[x];
        for (long long i = x; i > 0; i--) Facinv[i-1] = Facinv[i]*i;
    }

    mint get(int n, int k) {
        if (k < 0 || k > n || n < 0) return 0;
        return Fac[n]*Facinv[k]*Facinv[n-k];
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int H,W,N; cin >> H >> W >> N;
    H--; W--;
    vector<pii> A(N);
    rep(i,N) {
        cin >> A[i].first >> A[i].second;
        A[i].first--; A[i].second--;
    }

    ModCombination MC(H+W);
    sort(all(A));
    vector<mint> dp(N);
    rep(i,N) {
        int r,c;
        tie(r,c) = A[i];
        dp[i] -=MC.get(r+c,c);
        rep(j,i) {
            int s,d;
            tie(s,d) = A[j];
            dp[i] -= dp[j]*MC.get(r+c-s-d,c-d);
        }
    }

    mint ans = MC.get(H+W,H);
    rep(i,N) ans += dp[i]*MC.get(H+W-A[i].first-A[i].second,H-A[i].first);

    cout << ans.a << endl;
}

Measured memory_bytes: 3456
N, W = map(int, input().split())
v, w = [0] * N, [0] * N
for i in range(N):
	v[i], w[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
#print(dp)
print(dp[N][W])


Measured memory_bytes: 41888
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <assert.h>
#include <numeric>
#include <iomanip>
#define rep(i, a, b) for (int(i) = (a); i < (b); i++)
using namespace std;

using ll = long long;

typedef pair<int, int> P;

const int INF = 100000000;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll MOD = 1000000007;

ll pow_mod(ll x, ll y, ll mod)
{
	ll ans=1;
	for(;y>0;y>>=1){
		if(y&1)(ans*=x)%=mod;
		(x*=x)%=mod;
	}
	return ans;
}

string s;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	//問題文中の添え字が0-indexか1-indexか確認!
	cin >> s;
	int n = s.size();
	int cnt = 0;
	rep(i,0,n){
		if(s[i]=='o')
			cnt++;
	}
	if(cnt+15-n>=8)
		cout << "YES";
	else{
		cout << "NO";
	}
	return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
m = map(int,read().split())
XY = zip(m,m)

in_edge = [[] for _ in range(N+1)]
out_edge = [[] for _ in range(N+1)]
for x,y in XY:
    out_edge[x].append(y)
    in_edge[y].append(x)

out_deg = [len(x) for x in out_edge]

stack = [i for i,x in enumerate(out_deg[1:],1) if x==0]

dp = [0] * (N+1)
while stack:
    c = stack.pop()
    for p in in_edge[c]:
        y = dp[c]+1
        if dp[p] < y:
            dp[p] = y
        out_deg[p] -= 1
        if not out_deg[p]:
            stack.append(p)

answer = max(dp)
print(answer)

Measured memory_bytes: 42488
# -*- coding: utf-8 -*-
import sys
N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
B=[ map(int, sys.stdin.readline().split()) for _ in range(M) ]
B.sort(key=lambda x:-x[1] )

n=N
L=[]    #Bから降順でN個選ぶ
for cards,value in B:
    if cards<=n:    #カード全てがn枚に収まる場合
        L+=[ value for _ in range(cards) ]
        n-=cards
    else:    #カード全てがn枚に収まさらない場合
        L+=[ value for _ in range(n) ]
        n=0
        break
A+=L
A.sort(reverse=True)
print sum(A[:N])

Measured memory_bytes: 63452
def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()

Measured memory_bytes: 126408