akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

template <typename T>
T pow(T a, T n, T m){
	T r = 1;
	while(n){
		if(n & 1) (r *= a) %= m;
		(a *= a) %= m;
		n >>= 1;
	}
	return r;
}

int main(){
	int64_t n, m = 1e9 + 7;
	cin >> n;
	int64_t a[n + 1], puni[n + 1], fst, snd;
	fill(puni, puni + n + 1, -1);
	for(int64_t i = 0; i < n + 1; i++){
		cin >> a[i];
		if(puni[a[i]] != -1){
			fst = puni[a[i]];
			snd = i;
		}
		puni[a[i]] = i;
	}
	int64_t fact[n + 2], fact_rev[n + 2];
	fact[0] = 1;
	for(int64_t i = 1; i < n + 2; i++) fact[i] = (fact[i - 1] * i) % m;
	fact_rev[n + 1] = pow(fact[n + 1], m - 2, m);
	for(int64_t i = n; i >= 0; i--) fact_rev[i] = fact_rev[i + 1] * (i + 1) % m;
	cout << n << endl;
	for(int64_t k = 2; k <= n + 1; k++){
		cout << (fact[n + 1] * fact_rev[k] % m * fact_rev[n + 1 - k] % m - ((k - 1 <= fst + n - snd) ? fact[fst + n - snd] * fact_rev[k - 1] % m * fact_rev[fst + n - snd - (k - 1)] % m : 0) + m) % m << endl;
	}
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int a[n];
    int amari[n+1];
    amari[0]=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        amari[i+1]=(amari[i]+a[i])%m;
    }
    sort(amari,amari+n+1);
    long long ans=0;
    long long x=1;
    for(int i=0;i<n;i++){
        if(amari[i]==amari[i+1])x++;
        else{
            ans+=x*(x-1)/2;
            x=1;
        }
    }
    cout<<ans+x*(x-1)/2<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>

int main(){
  int table[100][100];
  int r,c,psum=0,asum=0;

  scanf("%d %d",&r,&c);

  for(int i=0; i < r; i++){
    for(int j=0; j < c; j++){
      scanf("%d",&table[i][j]);
    }
  }

  for(int i=0; i< r; i++){
    psum=0;
    for(int j=0; j< c; j++){
      printf("%d ",table[i][j]);
      psum+=table[i][j];
      asum+=table[i][j];
    }
    printf("%d\n",psum);
  }
  for(int i=0; i< c; i++){
    psum=0;
    for(int j=0; j< r; j++){
      psum+=table[j][i];
    }
    printf("%d ",psum);
  }
  printf("%d\n",asum);
}



Measured memory_bytes: 2740
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <math.h>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define DEBUG
#define fi first
#define se second
#define pqueue priority_queue
#define pb(x) push_back(x)
#define endl '\n'
#define all(x) x.begin(), x.end()
#define int long long
#define mk(a, b) make_pair(a, b)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ull> vull;
typedef vector<ll> vll;
// typedef tuple<int, int, int> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector< vector<int> > vvi;
typedef vector<char> vc;

const int INF = 1e9;
const ll INFLL = 1e16;
const int MOD = 1000000007;
const int MAXN = 3e5;
//const ld eps = 1e-6;
const ld eps2 = 1e-9;
const int MOD2 = 998244353;
const int dosz = 5e5;
const int SZ = (1<<18);
const ld PI = atan2l(0, -1);


void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
        // freopen("a.in", "r",stdin);
#else
       // freopen("substrcmp.in", "r", stdin);
       // freopen("substrcmp.out", "w", stdout);
#endif
}

int binpow(int n, int k){
    if(k==0){
        return 1;
    } else if(k&1){
        return binpow(n, k-1)*n%MOD;
    } else{
        int b = binpow(n, k/2);
        return b*b%MOD;
    }
}

void solve(){
    int n, a, b;
    cin >> n >> a >> b;
    int ans = binpow(2, n);
    int first = 1;
    for(int i=n; i>=n-a+1; i--){
        first *= i;
        first %= MOD;
    } 
    int sec = 1;
    for(int i=n; i>=n-b+1; i--){
        sec *= i;
        sec %= MOD;
    }
    int first_del = 1;
    for(int i=1; i<=a; i++){
        first_del *= i;
        first_del %= MOD;
    }
    int second_del = 1;
    for(int i=1; i<=b; i++){
        second_del *= i;
        second_del %= MOD;
    }
    ans--;
    // cout << ans << endl;
    first *= binpow(first_del, MOD-2);
    first %= MOD;
    // cout << first << endl;
    sec *= binpow(second_del, MOD-2);
    sec %= MOD;
    // cout << sec << endl;
    ans = (((ans+MOD)-first)%MOD + MOD)%MOD;
    ans = (((ans+MOD)-sec)%MOD + MOD)%MOD;
    cout << ans << endl;
}

signed main() {
    fast_io();
    int q = 1;
    // cout << fixed << setprecision(6);
    // cin >> q;
    // cout << 1 << endl;
    while(q--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
k, n = map(int, input().split())
a = list(map(int, input().split()))

max_dist = 0
for i in range(n-1):
	cur_dist = a[i+1] - a[i]
	if cur_dist > max_dist:
		max_dist = cur_dist

cur_dist = k + a[0] - a[-1]
if cur_dist > max_dist:
	max_dist = cur_dist

print(k - max_dist)


Measured memory_bytes: 77388
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    queue<Int> que;
    for (int i = 1; i < 10; i++) {
        que.push(i);
    }

    for (int i = 1; i < k; i++) {
        Int x = que.front();
        que.pop();

        if (x % 10 != 0) {
            que.push(10 * x + (x % 10) - 1);
        }
        que.push(10 * x + (x % 10));
        if (x % 10 != 9) {
            que.push(10 * x + (x % 10) + 1);
        }
    }

    cout << que.front() << endl;

    return 0;
}


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

int main(int argc, char const* argv[])
{
  int n;
  std::cin >> n;

  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  std::sort(a.begin(), a.end(), std::greater<int>());

  long alice = 0;
  long bob = 0;
  for (int i = 0; i < n; ++i) {
    if (0x1 & i) {
      bob += a[i];
    } else {
      alice += a[i];
    }
  }

  std::cout << alice - bob << std::endl;

  return 0;
}

Measured memory_bytes: 256
#define DBG 0 //submit 0
#define ll long long
#if DBG
    #include <algorithm>
    #include <array>
    #include <ctime>
    #include <cstdlib>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <iostream>
    #include <cmath>
    #include <queue>
    #include <numeric>
#else
    #include <bits/stdc++.h>
#endif
 
using namespace std;
 
 
int main(){
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(i%2==0) cout << s[i]; 
    }
    cout << endl;
    //cout << (flag ? "Yes" : "No") << endl;
    //cout << ans << endl;
}


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

int main() {
    int N; cin >> N;
    map<int, int> d;
    for (int i = 0; i < N; i++) {
        int a; cin >> a;
        d[a] ++;
    }   
    cout << d.size() << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int ans = 0;
    int n;
    int dp[100004][3], a[100004], b[100004], c[100004];
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    dp[1][0] = a[1];
    dp[1][1] = b[1];
    dp[1][2] = c[1];
    for (int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i];
    }
    ans = max(dp[n][0], max(dp[n][1], dp[n][2]));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
long long arr[1000000];
int main()
{
	long long n,i,j,f;
	f=0;
	cin>>n;
	for (i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	for (i=0;i<n;i++)
	{
		if (arr[i]%2==0)
		{
			if (arr[i]%3!=0 && arr[i]%5!=0)
			{
				f=1;
			}
		}
	}
	if (f==1)
	{
		cout<<"DENIED"<<endl;
	}
	else
	{
		cout<<"APPROVED"<<endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<cctype>
#include<math.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b){
    ll r;
    while(a%b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return b;
}
int main(){
    ll N,K;
    cin >> N >> K;
    ll A;
    cin >> A;
    ll l=A,m=A;
    ll i;
    for(i=0;i<N-1;i++){
        cin >> A;
        l=gcd(l,A);
        m=max(m,A);
    }
    if(K<=m&&K%l==0)cout << "POSSIBLE"<<endl;else cout << "IMPOSSIBLE";
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define N 100000
int n;
int A[N];
int Partition(int, int);
int main(){
	int i;
	int p=0;
	int r;
	int ans;
	scanf("%d", &n);
	for( i=0; i<n; i++ ){
		scanf("%d", &A[i]);
	}
	r=n-1;
	ans=Partition(p, r);
	for( i=0; i<ans; i++ ) printf("%d ", A[i]);
	printf("[%d] ", A[ans]);
	for( i=ans+1; i<n; i++ ){
		printf("%d", A[i]);
		if( i+1 < n) printf(" ");
	}
	printf("\n");
	return 0;
}

int Partition(int p, int r){
	int i;
	int j;
	int tmp;
	int x;
	x=A[r];
	i=p-1;
	for( j=p; j<=r-1; j++ ){
		if( A[j] <= x ){
			i++;
			tmp=A[j];
			A[j]=A[i];
			A[i]=tmp;
		}
	}
	tmp=A[r];
	A[r]=A[i+1];
	A[i+1]=tmp;
	return i+1;
}

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

using ll = long long int;
using P = pair<int, int>;
using P3 = pair<int,P>;
using PP = pair<P, P>;
constexpr int INF = 1<<29;
constexpr ll MOD = ll(1e9)+7;
constexpr int di[] = {0,1,0,-1};
constexpr int dj[] = {1,0,-1,0};


int main(){
    int n, k;
    cin >> n >> k;
    vector<double> a(n+1);
    for(int i=0;i<n;i++){
        double p;
        cin >> p;
        a[i+1] = (p+1)/2;
    }
    for(int i=0;i<n;i++){
        a[i+1] += a[i];
    }
    double ans = 0;
    for(int i=0;i<=n-k;i++){
        ans = max(ans, a[i+k]-a[i]);
    }
    printf("%.8lf\n", ans);
    return 0;
}



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

int main(){
  int A,B,C,X,ans=0;
  cin >> A >> B >> C >> X;
  X = X / 50;
  for(int i = 0; i < A+1 ; i++){
    for(int j = 0; j < B+1 ; j++){
      if(0 <= X-(10*i+2*j)&& X-(10*i+2*j)<C+1)
        ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
use std::io::*;
use std::cmp::*;

fn main() {
    let mut line = String::new();
    let _ = stdin().read_line(&mut line);
    let v: Vec<&str> = line.split_whitespace().collect();
    let a: i32 = v[0].parse().unwrap();
    let b: i32 = v[1].parse().unwrap();
    let c: i32 = v[2].parse().unwrap();
    println!("{}", max(0, c-a+b));
}

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

public class Program{
  public static void Main(){
    var hw = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    var a = new sbyte[hw[0],hw[1]];
    for(var i=0; i<hw[0]; i++){
      var l = Console.ReadLine();
      for(var j=0; j<hw[1]; j++) a[i,j] = (sbyte) ( l[j]=='#'?-1:0);
    }
    for(var i=0; i<hw[0]; i++){
      for(var j=0; j<hw[1]; j++){
        if(a[i,j]!=-1){
          a[i,j] += (sbyte) ((i!=0&&j!=0)?(a[i-1,j-1]==-1?1:0):0);
          a[i,j] += (sbyte) (i!=0?(a[i-1,j]==-1?1:0):0);
          a[i,j] += (sbyte) ((i!=0&&j!=hw[1]-1)?(a[i-1,j+1]==-1?1:0):0);

          a[i,j] += (sbyte) (j!=0?(a[i,j-1]==-1?1:0):0);
          a[i,j] += (sbyte) ((j!=hw[1]-1)?(a[i,j+1]==-1?1:0):0);

          a[i,j] += (sbyte) ((i!=hw[0]-1&&j!=0)?(a[i+1,j-1]==-1?1:0):0);
          a[i,j] += (sbyte) ((i!=hw[0]-1)?(a[i+1,j]==-1?1:0):0);
          a[i,j] += (sbyte) ((i!=hw[0]-1&&j!=hw[1]-1)?(a[i+1,j+1]==-1?1:0):0);
        }
        Console.Write("{0}", (a[i,j]==-1)?"#":a[i,j].ToString());
      }
      Console.Write("\n");
    }
  }
}


Measured memory_bytes: 13268
#include <stdio.h>

int main(){
  int a,b,c,d,r;
  double f;
  scanf("%d %d",&a,&b);
  c=a/b;
  r=a%b;
  f=(double)a/b;
  printf("%d %d %f\n",c,r,f);
  return 0;
}

Measured memory_bytes: 636
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j;
    long long int n;
    cin>>n;
    long long int a[n+1]={0};
    long long int ans=0;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j+=i)
            a[j]++;
    }
     for (int i = 1; i <= n; i++) {
       // cout<<a[i]<<endl;
        ans+=(i*a[i]);
     }
     cout<<ans<<endl;

}


Measured memory_bytes: 81688
import heapq

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

uvab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(N)]

for i in range(M):
    uvab[i][0] -= 1
    uvab[i][1] -= 1

railways = [[] for _ in range(N)]
max_a = 0
for u, v, a, b in uvab:
    railways[u].append((v, a, b))
    railways[v].append((u, a, b))
    max_a = max(max_a, a)
del uvab

max_silver = max_a * (N - 1)

ans = [-1] * N
d = dict()
d[(S, 0)] = 0  # silver, station
Q = [(0, S, 0)]  # time, silver, station
sum_reached = 0
reached = [False] * N

while Q:
    t, sv, st = heapq.heappop(Q)
    if not reached[st]:
        ans[st] = t
        reached[st] = True
        sum_reached += 1
        if sum_reached == N:
            break

    new_key = (min(max_silver, sv + cd[st][0]), st)
    new_value = t + cd[st][1]
    if new_key not in d or d[new_key] > new_value:
        d[new_key] = t + cd[st][1]
        heapq.heappush(Q, (new_value, *new_key))

    for dist, a, b in railways[st]:
        if sv >= a:
            new_key = (sv - a, dist)
            new_value = t + b
            if new_key not in d or d[new_key] > new_value:
                d[new_key] = new_value
                heapq.heappush(Q, (new_value, *new_key))

print(*ans[1:], sep="\n")


Measured memory_bytes: 36232
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long int llint;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int main(){
    int n; cin >> n;
    string s; cin >> s;
    map<char,int> mp;
    for(int i = 0; i < n; i++){
        mp[s[i]]++;
    }
    ll ans = 1;
    for(char t = 'a'; t <= 'z'; t++){
        if(mp[t] == 0) continue;
        ans *= (mp[t] + 1);
        ans %= MOD;
    }
    cout << ans-1 << endl;
}

 

Measured memory_bytes: 512
# include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000; // 10^9

int main()
{
  int N;
  cin >> N;
  
  vector<int> X(N);
  for (int i=0; i < N; i++)
  {
    cin >> X[i];
  }
  
  int ans = inf;
  
  for (int j = 1; j < 100; j++)
  {
    int cost = 0;
  	for (int i=0; i < N; i++)
    {
      int sc = j - X[i]; 
      cost += (sc * sc);
    }
    ans = min (ans, cost);
  }
  
  cout << ans << endl;
  return 0;
}

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

int main(void)
{
  int c = 0;
  int n;
  cin >> n;
  int a[n];
  int b[n];
  int max;
  int min;
  cin >> a[0] >> b[0];
  max = 0;
  min = 0;
  for ( int i=1; i<n; i++ ) {
    cin >> a[i] >> b[i];
    if ( a[i] > a[max] ) { max = i; }
    if ( a[i] < a[min] ) { min = i; }
  }
  c = a[max];
  for ( int i=b[max]-1; i>=0; i-- ) { c++; }
  cout << c << endl;
  return 0;
}

Measured memory_bytes: 1656
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

int compare_int(const void* a, const void* b) { return *(int*) a - *(int*) b; }

int n, dp[31];

int func(int p) {
	if (p == n) {
		return 1;
	}
	int cnt = 0;
	for (int i = p + 1; n >= i && 3 + p >= i; i++) {
		if (dp[i] == -1) dp[i] = func(i);
		cnt += dp[i];
	}
	return cnt;
}

int main() {
	while (scanf("%d", &n) != EOF) {
		if (n == 0) return 0;
		memset(dp, -1, sizeof(dp));
		printf("%d\n", ((func(0)+9) / 10 + 364) / 365);
	}
}

Measured memory_bytes: 1028
#include "bits/stdc++.h"
#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define sqr(x) (x) * (x)
#define cube(x) (z) * (z) * (x)
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))
#define itn int

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

template <class T = int>
int in() {
  T x;
  cin >> x;
  return x;
}

signed main() {
  int N = in();
  vector<int> s(N);
  rep(i, N) {
    cin >> s[i];
  }
  int sum = accumulate(ALL(s), 0LL);
  if (sum % 10) {
    cout << sum << endl;
    return 0;
  }
  sort(ALL(s));
  rep(i, N) {
    if ((sum - s[i]) % 10) {
      cout << sum - s[i] << endl;
      return 0;
    }
  }
  cout << 0 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <functional>
using namespace std;

int main()
{
	int a, b, c;
	int ans;
	char str[9];
	
	cin >> c;
	for(int i = 0; i < c; i++ )
	{
		cin >> str;
		sort(str, str + 8);
	
		stringstream ss;
		ss << str;
		ss >> a;
	
		sort(str, str + 8, greater<int>());
	
		stringstream tt;
		tt << str;
		tt >> b;
	
		cout << b - a << endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 1240
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;

const int root = 646;

const int root_1 = 208611436;

const int root_pw = 1<<20;

int mult(int a, int b) {
    return (1LL * a * b) % mod;
}

int pw(int a, int b) {
    if (b == 0) return 1;
    if (b & 1) return mult(a, pw(a, b - 1));
    int res = pw(a, b / 2);
    return mult(res, res);
}

int sub(int a, int b) {
    int s = a - b;
    if (s < 0) s += mod;
    return s;
}

int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}

const int maxN = 9 * (int)1e5 + 100;

int fact[maxN], invfact[maxN], inv[maxN];
int pw3[maxN];

void init() {
    inv[1] = invfact[1] = invfact[0] = fact[0] = fact[1] = 1;
    for (int i = 2; i < maxN; i++) {
        fact[i] = mult(fact[i - 1], i);
        inv[i] = mult(inv[mod % i], mod - mod / i);
        invfact[i] = mult(invfact[i - 1], inv[i]);
    }
    pw3[0] = 1;
    for (int i = 1; i < maxN; i++) {
        pw3[i] = mult(pw3[i - 1], 3);
    }
}

int cnk(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return mult(fact[n], mult(invfact[k], invfact[n - k]));
}

int invNumber(int a) {
    return pw(a, mod - 2);
}

struct query{
    int L, R, coef;
    query(int _L, int _R, int _coef) : L(_L), R(_R), coef(_coef) {}
};
const int BLOCK = 500;
bool cmp(query& a, query& b) {
    return make_pair(a.L / BLOCK, a.R) < make_pair(b.L / BLOCK, b.R);
}
int L, R, res;
void incL() {
    L++;
    res = sum(res, cnk(R, L));
}
void decL() {
    res = sub(res, cnk(R, L));
    L--;
}
void incR() {
    res = sum(res, res);
    res = sub(res, cnk(R, L));
    R++;
}
const int inv2 = (mod + 1) / 2;
void decR() {
    R--;
    res = sum(res, cnk(R, L));
    res = mult(res, inv2);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    init();
    int n, m, k;
    cin >> n >> m >> k;
    int tot = n + m + k;
    vector < query > all1, all2;
    for (int where = n; where <= tot; where++) {
        int cur = cnk(where - 1, n - 1);
        cur = mult(cur, pw3[tot - where]);
        int from = where - n - k;
        int to = m;
        to = min(to, where - n);
        from = max(from, 0);
        if (from > to) continue;
        all2.emplace_back(to, where - n, cur);
        if (from) all1.emplace_back(from - 1, where - n, sub(0, cur));
    }
    L = 0;
    R = 0;
    res = 1;
    int ans = 0;
    for (auto it : all2) {
        while (R < it.R) incR();
        while (L > it.L) decL();
        while (R > it.R) decR();
        while (L < it.L) incL();

        ans = sum(ans, mult(it.coef, res));
    }
    for (auto it : all1) {
        while (R < it.R) incR();
        while (L > it.L) decL();
        while (R > it.R) decR();
        while (L < it.L) incL();
        ans = sum(ans, mult(it.coef, res));
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 33644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, ans;
multiset<int> st;//因为数据可能重复，所以用multiset

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int x;
		scanf("%d", &x);
		st.insert(x);
	}
	while (!st.empty()) {
		ll v = *--st.end();//取st最后一位数据
		st.erase(--st.end());//将最后一位数据抹去，避免下面find找到自己
		for (int i = 0; i <= 30; ++i) {//2^32是int范围内的极限,循环int内的2的幂
			ll t = (1 << i) - v;
			if (st.find(t) != st.end()) {//如果t在st中存在，抹去，ans++，并且break
				++ans; st.erase(st.find(t)); break;
			}
		}
	}
	printf("%d", ans);
}


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

int main() {
  int n;
  cin >> n;
  vector<int>a(n);
  rep(i,n) cin >> a[i];
  int cnt = 0;
  int cnt2 = 0;
  rep(i,n){
    if(a[i]%2==0){
      cnt++;
      if(a[i]%3==0 || a[i]%5==0) cnt2++;
      else continue;
    }
  }
  if(cnt==cnt2) puts("APPROVED");
  else puts("DENIED");
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
const int INF = 1001001001;

int main() {
    ll N, mn = 200000+1, ans=0;

    cin >> N;

    vector<int> P(N);

    rep(i, N) {
        cin >> P[i];
        if(mn>P[i]) {
            ans++;
            mn = P[i];
        }
    }

    cout << ans << endl;

    return 0;
    
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);++i)
#define mod 1000000007

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

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint pow2(int n) {
  if (n == 0) return 1;
  mint x = pow2(n/2);
  x *= x;
  if (n%2 == 1) x *= 2;
  return x;
}

mint choose(int n, int a) {
  mint x = 1, y = 1;
  rep(i,a) {
    x *= n-i;
    y *= i+1;
  }
  return x/y;
}

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  mint ans = pow2(n);
  ans -= 1;
  ans -= choose(n,a);
  ans -= choose(n,b);
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  char A[3],B[3];
  int i=0;
  int count=0;
    scanf("%s",A);
    scanf("%s",B);
  for(i=0;i<=2;i++)
  {
    if(A[i]==B[i]) 
    {
         count=count+1;
    }
  }
    printf("%d",count);
    return 0;
       }


Measured memory_bytes: 128
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>

using namespace std;
 
typedef long long ll;


int main()
{
    ll n , m;
    cin >> n >> m;
    vector<ll> v;
    v.assign(n , -1);
    set<ll> s1 , s2;
    ll a , b;
    for(ll i = 0 ; i < m ; i++){
        cin >> a >> b;
        if(a == 1){
            s1.insert(b);
        } 
        if(b == n){
            s2.insert(a);
        }
    }
    for(auto itr = s1.begin(); itr != s1.end(); ++itr) {
        if(s2.count(*itr) > 0){
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    
    cout << "IMPOSSIBLE" << endl;

    return 0;
}

Measured memory_bytes: 11136
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    ans=0
    for i in range(N):
        l,r=MI()
        ans+=r-l+1
    print(ans)
        

main()


Measured memory_bytes: 39024
import sys
N = int(input())
a = sorted([(x+l, x-l) for x, l in (map(int, l.split()) for l in sys.stdin)])

last = a[0][0]
ans = 1

for r, l in a[1:]:
    if(last <= l):
        ans += 1
        last = r
print(ans)

Measured memory_bytes: 17788
count = 0
N = int(input())

def yaku(k):
    small = 0
    for j in range(1,k+1):
        if k % j == 0:
            small += 1
    if small == 8:
        return 1
    else:
        return 0

for i in range(N + 1):
    if i % 2 == 1:
        count += yaku(i)

print(count)

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

  cin >> x;

  if (x >= 400 && x <= 599)
    cout << "8";
  else if (x >= 600 && x <= 799)
    cout << "7";
  else if (x >= 800 && x <= 999)
    cout << "6";
  else if (x >= 1000 && x <= 1199)
    cout << "5";
  else if (x >= 1200 && x <= 1399)
    cout << "4";
  else if (x >= 1400 && x <= 1599)
    cout << "3";
  else if (x >= 1600 && x <= 1799)
    cout << "2";
  else if (x >= 1800 && x <= 1999)
    cout << "1";
}


Measured memory_bytes: 3672
#include <stdio.h>

int main()
{
    double l, vertical, horizontal, height, volume;

    scanf( "%lf", &l);

    //if(l%3 = 0) 
        volume = (l/3) * (l/3) * (l/3);
    /*else 
        {
           
        }*/
    printf( "%.12lf\n", volume );
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main(void){
    // Your code here!
    int h,w,i,j,n;
    while(scanf("%d %d\n", &h, &w) != EOF){
    if(h==0 && w==0){
        break;
    }
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            n=i+j;
            if(n % 2 == 0){
                printf("#");
            }
            else{
                printf(".");
            }
        }
    printf("\n");
    }
    printf("\n");
    }
    
    return 0;
}



Measured memory_bytes: 2036
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let s: Vec<char> = sc.chars();
    let t: Vec<char> = sc.chars();

    let mut ret: String = String::with_capacity(n * 2);
    for i in 0..n {
        ret.push(s[i]);
        ret.push(t[i]);
    }
    println!("{}", ret);

}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

int main(){
    ll n,m,a = 1;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        if(a*2 < (m + a)){
            a *= 2;
        }else{
            a += m;
        }
    }
    cout << a << endl;
    return 0;
}



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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		for(int i = 0 ; i < N ; i++) {
			A[i] = sc.nextInt();
		}
		Arrays.sort(A);
		long ans = 1;
		//N人が偶数人か奇数人か
		if(N % 2 == 0) {
			//並び方があり得るかを検証
			for(int i = N - 1 ; i > 0 ; i -= 2) {
				if(A[i] != A[i - 1]) {
					System.out.println(0);
					return;
				}
			}
			for(int i = 0 ; i < N / 2 ; i++) {
				ans = ans * 2 % 1000000007;
			}
			System.out.println(ans);
		} else {
			//並び方があり得るかを検証
			if(A[0] != 0) {
				System.out.println(0);
				return;
			}
			for(int i = 1 ; i < N ; i += 2) {
				if(A[i] != A[i + 1]) {
					System.out.println(0);
					return;
				}
			}
			//何通りの並べ方があるか検証
			for(int i = 0 ; i < N / 2 ; i++) {
				ans = ans * 2 % 1000000007;
			}
			System.out.println(ans);
		}
	}
}


Measured memory_bytes: 52408
h,w=map(int,input().split())

v=[[0 for j in range(w+1) ] for i in range(h+1)]

for i in range(h):
	row = list(map(int,input().split()))
	for j in range(w):
		v[i][j] = row[j]
		v[i][w] += v[i][j]
		v[h][j] += v[i][j]
		v[h][w] += v[i][j]

for i in range(h+1):
	for j in range(w):
		print(v[i][j],end=" ")
	print(v[i][w])



Measured memory_bytes: 6220
#include<stdio.h>
int main(void)
{
	int l,a,b,c,d,x,y,n;
	scanf("%d %d %d %d %d",&l,&a,&b,&c,&d);
	x=a/c;
	y=b/d;
	if(0!=a%c){
		x+=1;
	}
	if(0!=b%d){
		y+=1;
	}
	if(x>y){
		n=l-x;
	}
	else{
		n=l-y;
	}
	printf("%d\n",n);
	return 0;
}



Measured memory_bytes: 2108
#n:1からnまでの数
#x:合計値

while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break
    else:
        cnt = 0
        for i in range(1, n+1):
            for j in range(i+1, n+1):
                for k in range(j+1, n+1):
                    if  (i + j + k) == x:
                        cnt += 1
    print(cnt)


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

using namespace std;
const int Max_N=200010;

bool flag[Max_N];
int c[Max_N];
vector<int> G[Max_N];
map<int,int> M;

void pl(int n, int x){
  c[n]+=x;
  flag[n]=true;
  rep(i,G[n].size()){
    int j=G[n][i];
    if(flag[j]==false) pl(j,M[j]+x);
  }
}

int main(){
  int N, Q;
  cin >> N >> Q;
  rep(i,N-1){
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  rep(i,Q){
    int p, x;
    cin >> p >> x, p--;
    M[p]+=x;
  }
  rep(i,N) flag[i]=false;
  pl(0,M[0]);
  rep(i,N-1) cout << c[i] << " ";
  cout << c[N-1] << endl;
  
  return 0;
}

Measured memory_bytes: 42368
from math import gcd
from functools import reduce
from itertools import product

def resolve():
  K = int(input())
  A, B = map(int, input().split(" "))

  result = False
  for i in range(A, B+1):
    if i%K == 0:
      result = True
      break
  print("OK" if result else "NG")

if __name__ == "__main__":
  resolve()


Measured memory_bytes: 67480
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
typedef pair<int,int> P;
#define mod 1000000007
const double pi=3.141592653589793;


int main(){
    int a,b,x;
    cin>>a>>b>>x;
    double h=2.0*x/a/b;
    if(h<=a){
        double ans=atan(a*b*b/2.0/x)*180/pi;
        printf("%.12lf\n",ans);
        return 0;
    }
    else {
        double ans=atan(2.0*b/a-2.0*x/a/a/a)*180/pi;
        printf("%.12lf\n",ans);
        return 0;
    }
}

Measured memory_bytes: 512
import java.util.*;

public class Main{
   public static void main(String[] args){
      Scanner sc= new Scanner(System.in);
      int a=sc.nextInt();
      if(a==3||a==5||a==7){
         System.out.println("YES");
      }else{
         System.out.println("NO");
      }
   }

}

Measured memory_bytes: 23764
#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <tuple>
#include <regex>
#include <map>
#include <cstdint>
#include <set>
#include <deque>
#include <iomanip>
#include <queue>

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

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

#define EPS (1e-7)
#define ALL(x) begin(x), end(x)

bool isA(char c) {
	return c == 'A';
}
bool isD(char c) {
	return c == 'D';
}

ll exchageCount(const string& s) {
	// Aのみ　Dのみ　はノーカウント
	if (all_of(ALL(s), isA) || all_of(ALL(s), isD)) {
		return 0;
	}
	// Dの数と場所
	vector<ll> vec;
	for (size_t i = 0; i < s.size(); i++) {
		if (s[i] == 'D') {
			vec.push_back(i);
		}
	}
	// 距離を比較する
	vector<ll> expect = vec;// copy
	iota(ALL(expect), 0LL);
	ll count = 0;
	for (size_t i = 0; i < vec.size(); i++) {
		count += vec[i] - expect[i];
	}
	return count;
}

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

	// すべてのBCをDにする。
	string S_kai;
	for (size_t i = 0; i < s.size(); i++) {
		if (i < s.size() - 1 && s[i] == 'B' && s[i+ 1] == 'C') {
			S_kai.push_back('D');
			i++;
		} else {
			S_kai.push_back(s[i]);
		}
	}

	// AとDが連続する箇所は入れ替えできるはずだ
	string temp;
	ll ans = 0;
	for (size_t i = 0; i < S_kai.size(); i++) {
		if (S_kai[i] == 'A'|| S_kai[i] == 'D') {
			temp.push_back(S_kai[i]);
		} else {
			ans += exchageCount(temp);
			string temp2;
			swap(temp, temp2);
		}
	}
	if (temp.size() > 0) {
		ans += exchageCount(temp);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<pair<int,int>> v;
	for(int i=0;i<n;i++)
	{
		int a;
		cin >> a;
		v.push_back(make_pair(a,i));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++)
	{
		cout << v[i].second+1 << " ";
	}
}

Measured memory_bytes: 1780
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<stdbool.h>
#include<set>
#define N 1000000007
using namespace std;
typedef long long ll;
int num[100001];
int main(void) {
	string s;
	cin >> s;
	if ((s[0] == s[1]&&s[1] == s[2]) || (s[1] == s[2]&&s[2] == s[3]))cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep(i,n) rep2(i,0,n)
#define debug(x) cerr << x << endl
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<int>;
V(size_t) -> V<int>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1<<30;
const ll LINF = 1LL<<61;
const ll MOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    V<ll> a(n);
    rep(i,n) cin >> a[i];
    int s = 1+n%2;

    //3つまで飛ばして選べる
    //dp[i][j][k] := i-1番目までを見て、スキップをj回使い、直前の要素を使ったときの最大値
    auto dp = make_vec(n+1, s+1, 2, -LINF);
    dp[0][0][0] = 0;
    rep(i,n) rep(j,s+1)
    {
        int ni = i+1;
        
        //直前の要素をとった
        chmax(dp[ni][j][0], dp[i][j][1]);
        //a[i]をとる
        chmax(dp[ni][j][1], dp[i][j][0] + a[i]);
        //バックレ
        if(j < s) chmax(dp[ni][j+1][0], dp[i][j][0]);
    }
    ll ans = -LINF;
    if(n%2==1) rep2(i,1,s+1) rep(j,2) chmax(ans, dp[n][i][j]);
    else rep(i,s+1) rep(j,2) chmax(ans, dp[n][i][j]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 43856
#include <bits/stdc++.h>
using namespace std;
using Int = long long;

template <typename T> struct WeightedUnionFind{
  Int n;
  T d;
  vector<Int> r,p;
  vector<T> ws;
  WeightedUnionFind(){}
  WeightedUnionFind(Int sz,T d_):
    n(sz),d(d_),r(n,1),p(n),ws(n,d){iota(p.begin(),p.end(),0);}
  Int find(Int x){
    if(x==p[x]){
      return x;
    }else{
      Int t=find(p[x]);
      ws[x]+=ws[p[x]];
      return p[x]=t;
    }
  }
  T weight(Int x){
    find(x);
    return ws[x];
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y,T w){
    w+=weight(x);
    w-=weight(y);
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y),w=-w;
    r[x]+=r[y];
    p[y]=x;
    ws[y]=w;
  }
  T diff(Int x,Int y){
    return weight(y)-weight(x);
  }
};

int main(){
    Int n, m;
    cin >> n >> m;
    WeightedUnionFind<Int> wuf(n+1, 0);
    for(Int i=0;i<m;i++){
        Int l, r, d;
        cin >> l >> r >> d;
        l--, r--;
        if(wuf.same(l, r)){
            if(wuf.diff(l, r) != d){
                cout << "No" << endl;
                return 0;
            }
        }else wuf.unite(l, r, d);
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 2560
#pragma gcc optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,r,n) for(ll i=(ll)(r);i<(ll)(n);++i)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define pb(n) push_back(n)
#define endl '\n'
#define debug(x) cout << #x << " = " << (x) << endl
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c
#define VIN(V) for(int ii = 0; ii < (V).size(); ii++) {cin >> (V).at(ii);}
#define OUT(n) cout << n << endl
#define OUT2(n1,n2) cout << n1 << " " << n2 << endl
#define OUT3(n1,n2,n3) cout << n1 << " " << n2 << " " << n3 << endl
#define VOUT(V) REP(ii,(V).size()){cout << (V)[ii] << " ";} cout<<endl;
#define VOUT2(V) REP(jj,(V).size()){VOUT(V[jj])}
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vi > vvi;
typedef vector<pair<ll, ll> > vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;
const long long INF = numeric_limits<ll>::max();
const long long MOD = 1000000007;
const long double PI = 3.1415926;
template <class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
ll n, m, k, ans, sum, cnt = 0; string s; char c; bool flg;

int main(){
  cin.tie(0);ios::sync_with_stdio(false);
  IN(s);
  if (s[0]==s[1] || s[1]==s[2] || s[2]==s[3]) {
    OUT("Bad");
  } else {
    OUT("Good");
  }
}


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

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
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; }
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}

const ll INF = 1LL << 60;

ll n,m;
string s;
//Write From this Line

const int mod = 1e9+7;
int main()
{
	ll k ;
	cin >> n >> k ;
	if ( k % 2 == 0 ){
		ll a = n / k;
		ll b = ( n + (k / 2) )/ k;
		cout << a * a * a + b * b * b<< endl;
	}
	else{
		ll a = n / k ;
		cout << a * a * a <<endl;
	}
	//けんちょんさんの写経
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

namespace LogicSummoner
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = GetNumbersDouble();
            Console.WriteLine("{0:F8}", Math.Sqrt((line[0] - line[2]) * (line[0] - line[2]) + (line[1] - line[3]) * (line[1] - line[3])));
        }

        //static StreamReader Console = new StreamReader("input.txt");

        static int GetNumber()
        {
            return int.Parse(Console.ReadLine().Trim());
        }

        static double GetDounble()
        {
            return double.Parse(Console.ReadLine().Trim());
        }

        static int[] GetNumbersInt(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToArray();
        }

        static long[] GetNumbersLong(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => long.Parse(x)).ToArray();
        }

        static double[] GetNumbersDouble(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => double.Parse(x)).ToArray();
        }

        static string[] GetStrings(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).ToArray();
        }
    }
}

Measured memory_bytes: 10200
#include<bits/stdc++.h> 
#include<vector> 
#include<iterator> 
#include<deque> 
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i = 0; i <(n) ; i++)
#define rep2(i,s,n) for(long long i = (s); i(n) ; i++)
#define ll long long
#define INF 99999999999

int main(){
  int H,N;
  cin >>H>>N;

  vector<int> dp(H+1,INF);
  dp[0] = 0;

  rep(i,N){
    int A,B;
    cin >> A >> B;

    rep(j,H){
      int dj = min(H,j+A);
      dp[dj]=min(dp[dj],dp[j]+B); 
    }
  }
  cout << dp[H]  << endl;
  return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
h = list(map(int, input().split()))

ans = [float("inf")] * N
ans[0] = 0
for i in range(N-1):
    for j in range(1, K+1):
        if i + j > N - 1:
            continue
        ans[i+j] = min(ans[i+j], ans[i] + abs(h[i] - h[i+j]))
print(ans[-1])  

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

int main() {
	int n;
	while(cin >> n){
		int x = n / 100;
		if(n % 100 <= x * 5 )
			cout << 1 << endl;
		else cout << 0 << endl;
		
		
	}
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const double pi=acos(-1.0);
const ll mod=pow(10,9)+7;
const ll INF=pow(2,31)-1;
using str=string;
typedef pair<int,int> P;
typedef vector<int> vi;

ll gcd(ll a,ll b){
    ll v0=a,v1=b,v2=a%b;
    while(v2!=0){
        v0=v1;
        v1=v2;
        v2=v0%v1;
    }
    return v1;
}

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

int main(){
    int h,n;
    cin >> h >> n;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
    }
    int S=0;
    rep(i,n){
        S+=a[i];
    }
    if(S<h){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 640
/*{{{*/
#include<bits/stdc++.h>

typedef long long ll;

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

#define vl vector<ll>
#define pll pair<ll,ll>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;
/*}}}*/

int main() {
  ll x,n;
  cin >> x >> n;
  ll ans = 100000;
  vl a(n);
  REP(i,n) cin >> a[i];
  FOR(i,-200,200){
    bool contained = false;
    REP(j,n){
      if(i==a[j]) contained = true;
    }
    if(contained) continue;
    if(abs(x-i)<abs(x-ans)) ans = i;
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

using int64 = long long;
using vi = vector< int >;
using vii = vector< vi >;
const int mod = 1e9 + 7;


struct edge
{
  int u, v, cost;

  bool operator<(const edge &e) const
  {
    return (cost < e.cost);
  }
};

const int INF = 1 << 30;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};


int main()
{

  int N;
  cin >> N;
  vector< edge > edges;
  for(int i = 1; i < N; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    edges.emplace_back((edge) {a, b, c});
  }
  sort(begin(edges), end(edges));
  reverse(begin(edges), end(edges));

  UnionFind uf(N);
  vector< int64 > cost(N);
  vector< vector< int > > dsu(N);
  for(int i = 0; i < N; i++) {
    dsu[i].emplace_back(i);
  }
  vector< int64 > lazy(N);
  for(auto &e : edges) {

    e.u = uf.find(e.u);
    e.v = uf.find(e.v);
    if(dsu[e.u].size() < dsu[e.v].size()) {
      swap(e.u, e.v);
    }

    int64 sa = lazy[e.v] - lazy[e.u]; // e.u のほうが sa だけ多い
    int64 latte = 1LL * e.cost * uf.size(e.v);
    int64 malta = 1LL * e.cost * uf.size(e.u);

    while(!dsu[e.v].empty()) {
      cost[dsu[e.v].back()] += malta + sa - latte;
      dsu[e.u].emplace_back(dsu[e.v].back());
      dsu[e.v].pop_back();
    }
    lazy[e.u] += latte;
    lazy[e.v] = 0;
    uf.unite(e.u, e.v);
  }
  for(int i = 0; i < N; i++) {
    cout << cost[i] + lazy[uf.find(i)] << endl;
  }


}


Measured memory_bytes: 14068
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {
    int N;
    cin >> N;
    vector<int> b, ans;
    for (int i = 0; i < N; i++) {
        int temp;
        scanf("%d", &temp);
        b.push_back(temp);
    }

    for (int i = 0; i < N; i++) {
        int maximum = -1;
        for (int j = 0; j < b.size(); j++) {
            if (b[j] == j + 1) maximum = j + 1;
        }
        if (maximum == -1) {
            cout << -1 << endl;
            return 0;
        }
        ans.push_back(maximum);
        b.erase(b.begin() + maximum - 1);
    }
    if (ans.size() == N) {
        for (int i = ans.size() - 1; i >= 0; i--) {
            cout << ans[i] << endl;
        }
    }
    else cout << -1 << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] reds = new int[n][2];
        for(int i = 0; i < n; i++) {
        	reds[i][0] = sc.nextInt();
        	reds[i][1] = sc.nextInt();
        }

        int[][] blues = new int[n][2];
        for(int i = 0; i < n; i++) {
        	blues[i][0] = sc.nextInt();
        	blues[i][1] = sc.nextInt();
        }
        
        Arrays.sort(reds, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        Arrays.sort(blues, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    
        boolean[] visited = new boolean[n];
        int cnt = 0;
        int idx = -1;
        
        for(int i = 0; i < n; i++) {
        	int[] blue = blues[i];
        	idx = -1;
        	
        	for(int j = 0; j < n; j++) {
        		if(visited[j]) continue;
        		if(reds[j][0] < blue[0] && reds[j][1] < blue[1] && (idx == -1 || reds[j][1] > reds[idx][1])) {
                    idx = j;
        		}
        	}
        	
        	if(idx == -1) continue;
    		visited[idx] = true;
    		cnt++;
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 26964