akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (ll i = 0; i < (n); ++i)

using namespace std;
typedef long long ll;

struct mint{
    static const long long MOD = 1000000007;

    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const{
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const {
        return mint(v) -= a;
    }

    mint operator/(mint a) const {
        return mint(v) /= a;
    }

    mint pow(long long k) const {
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv(){return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

mint operator*(long long l, mint r){ return r * l; }

std::ostream& operator<<(std::ostream& stream, const mint& m){
    stream << m.v;
    return stream;
}

void solve(long long N, std::vector<unsigned long long> A){
    array<array<mint, 2>, 60> tmp;
    REP(i, 60){
        ll num1 = 0;
        for(auto x : A){
            num1 += ((x >> i) & 1) != 0;
        }
        tmp.at(i).at(1) = num1 * mint((1ULL << i) % mint::MOD);
        tmp.at(i).at(0) = ((ll)A.size() - num1) * mint((1ULL << i) % mint::MOD);
    }
    mint ans = 0;
    for(auto x : A){
        REP(i, 60){
            if(((x >> i) & 1ULL)){
                ans += tmp.at(i).at(0);
            }else{
                ans += tmp.at(i).at(1);
            }
        }
    }
    ans /= 2;
    cout << ans << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<unsigned long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%llu",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


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

int main(){
  ll n,k;
  cin >> n >> k;
  ll a,b;
  a = n%k;
  b = abs(a-k);
  cout << min(a,b) << endl;
  return 0;
}


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

int main() {
  
  int H, W;
  std::cin >> H >> W;
  
  int a[H][W];
  
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      std::cin >> a[i][j];
    }
  }
  
  int N = 0;
  std::vector<int> v;
  
  
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (a[i][j] % 2 == 1) {
        if (i == H - 1 && j == W - 1) {
          
        } else if (j != W - 1) {
          a[i][j]--;
          a[i][j + 1]++;
          v.push_back(i);
          v.push_back(j);
          v.push_back(i);
          v.push_back(j + 1);
          N++;
        } else {
          a[i][j]--;
          a[i + 1][j]++;
          v.push_back(i);
          v.push_back(j);
          v.push_back(i + 1);
          v.push_back(j);
          N++;
        }
      }
    }
  }
  
  std::cout << N << endl;
  for (int i = 0; i < 4 * N; i = i + 4) {
    std::cout << v[i] + 1 << " " << v[i + 1] + 1 << " " << v[i + 2] + 1 << " " << v[i + 3] + 1 << endl;
  }
  
  
    
  return 0;
}


Measured memory_bytes: 5104
#include<cstdio>
#include<cstring>
int main(){
    char s[15+5];
    scanf("%s",s);
    int n = strlen(s);
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(s[i]=='x') cnt++;
    }
    if(cnt>7) printf("NO\n");
    else printf("YES\n");
    return 0;
}

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--){
	    int a;
	    cin>>a;
	    cout<<(pow(a,1)) + (pow(a,2)) + (pow(a,3))<<endl;
    
    }
    return 0;
} 


Measured memory_bytes: 4184
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

void dfs(int target, unordered_map<int, vector<int>>& um, int parent, vector<int>& answer) {
    for (int child : um[target]) {
        if (child != parent) {
            answer[child] += answer[target];
            dfs(child, um, target, answer);
        }
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    unordered_map<int, vector<int>> um;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        um[a - 1].push_back(b - 1);
        um[b - 1].push_back(a - 1);
    }
    vector<int> answer(n, 0);
    for (int i = 0; i < q; ++i) {
        int p, x;
        cin >> p >> x;
        answer[p - 1] += x;
    }
    dfs(0, um, -1, answer);
    for (int i = 0; i < n; ++i) {
        cout << answer[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
}


Measured memory_bytes: 36424
import java.util.Scanner;

public class Main {
	static int map[][];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n,i,j,k,sum;
		while(true){
			n=sc.nextInt();
			if(n==0) break;
			map=new int[n+1][n+1];
			for(i=0;i<n;i++)
				for(j=0;j<n;j++)
					map[i][j]=sc.nextInt();
			//
			k=0;
			for(i=0;i<n;i++){
				sum=0;
				for(j=0;j<n;j++){
					sum+=map[i][j];
				}
				map[i][n]=sum;
				k+=sum;
			}
			
			for(j=0;j<n;j++){
				sum=0;
				for(i=0;i<n;i++){
					sum+=map[i][j];
				}
				map[n][j]=sum;
				//k+=sum;
			}
			
			map[n][n]=k;
			
			for(i=0;i<=n;i++){
				for(j=0;j<=n;j++){
					System.out.printf("%5d",map[i][j]);
				}
				System.out.println();
			}
		}//while
	}
}

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

const double EPS = 1e-10;

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b)))
		return 0;
	return a + b;
}

struct P {
	double x, y;
	P() {};
	P(double x, double y) : x(x), y(y) {
	}

	P operator + (P p) {
		return P(add(x, p.x), add(y, p.y));
	}

	P operator - (P p) {
		return P(add(x, -p.x), add(y, -p.y));
	}

	P operator * (double d) {
		return P(x * d, y * d);
	}

	P operator / (double d) {
		return P(x / d, y / d);
	}

	// 内積
	double dot(P p) {
		return add(x * p.x, y * p.y);
	}

	// 外積
	double det(P p) {
		return add(x * p.y, -y * p.x);
	}
};

// 線分上に点があるか
bool on_seg(P p1, P p2, P q) {
	return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0;
}

// 直線と直線の交点
P intersection(P p1, P p2, P q1, P q2) {
	return p1 + (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
}

// 2直線の直行判定
bool line_orth(P a1, P a2, P b1, P b2) {
	return fabs((a1 - a2).dot(b1 - b2)) < EPS;
}

// 2直線の垂直判定
bool line_paral(P a1, P a2, P b1, P b2) {
	return fabs((a1 - a2).det(b1 - b2)) < EPS;
}

int main(void) {
	P p[4];
	while ( cin >> p[0].x ) {
		cin >> p[0].y;
		for (int i = 1; i < 4; i++) {
			cin >> p[i].x >> p[i].y;
		}

		cout << (line_orth(p[0], p[1], p[2], p[3]) ? "YES" : "NO") << endl;
	}
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100000000;

int main()
{
   int h,a;
   cin >> h >> a;
   cout<<(h+a-1)/a<<endl;
   return 0;
}

Measured memory_bytes: 256
import math


def cnt(a: int, k: int):
    return a // k


def num(a, c, d):
    m_a_c = cnt(a, c)
    m_a_d = cnt(a, d)
    m_a_cd = cnt(a, c * d // math.gcd(c, d))
    return a - m_a_c - m_a_d + m_a_cd


a, b, c, d = map(int, input().split())
print(num(b, c, d) - num(a-1, c, d))


Measured memory_bytes: 9080
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pi pair<int, int>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define deb(x) cout << #x << ":" << x << endl;
/* freopen("input.txt", "r", stdin); */
/* freopen("output.txt", "w", stdout); */
const ll inf = 1e17 + 7, MOD = 1e7 + 9;
/* int count = 0; */
void f(int pos, int last, int n, int m, int *ans, vi a, int Q, vector<vi> q) {
	if(pos == n) {
		// calc score, max
		/* for(auto i: a) */
		/* 	cout << i << " "; */
		/* cout << "\n"; */
		/* ::count++; */
		int curr=0;
		for(int i=0;i<Q;i++) {
			if(a[q[i][1]-1] - a[q[i][0]-1] == q[i][2])
				curr += q[i][3];
		}
		*ans = max(curr, *ans);
		return;
	}
	for(int j=last;j<=m;j++) {
		a.PB(j);
		f(pos+1, j, n, m, ans, a, Q, q);
		a.pop_back();
	}
}

int main() {
	fastio();
	int n, m, Q;
	cin >> n >> m >> Q;
	vector<vi> q;
	int a, b, c, d;
	for(int i=0;i<Q;i++) {
		cin >> a >> b >> c >> d;
		q.PB({a, b, c, d});
	}
	int ans = 0;
	vi A;
	A.PB(1);
	f(1, 1, n, m, &ans, A, Q, q);
	cout << ans << "\n";
	/* cout << ::count << "\n"; */
	return 0;
}



Measured memory_bytes: 3680
K, A, B = map(int, input().split())


biscuits  = 1

if B - A > 2 and A <= K - 1:
    #最初にA枚までクッキーを増やす
    K -= A - 1
    biscuits += A - 1

    biscuits  += (B - A) * (K // 2)
    K -= (K // 2) * 2
    biscuits += K
else:
    biscuits  += K

print(biscuits)


Measured memory_bytes: 2940
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws FileNotFoundException {

//    Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner(System.in);

    int a = cin.nextInt();
    int b = cin.nextInt();
    int c = cin.nextInt();

    System.out.println(Math.min(b / a, c));


  }

}

Measured memory_bytes: 23252
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>

using namespace std;
typedef long long int ll;

int main()
{
	ll n;
	ll a[50];
	scanf("%lld", &n);
	for(int i=0; i<n; i++){
		scanf("%lld", &a[i]);
	}
	sort(a, a+n, greater<ll>());
  ll ans=0;
  if(a[0]<=1000){
    if(a[0]<=n-1){
      printf("%d\n", 0);
      return 0;
    }
    while(1){
      ll m=-1, im;
      for(ll j=0; j<n; j++){
        if(m<a[j]){
          m=a[j], im=j;
        }
      }
      for(ll i=0; i<n; i++){
        if(im==i){
          a[i]-=n;
        }else{
          a[i]++;
        }
      }
      ans++;
      bool e=0;
      for(ll j=0; j<n; j++){
        if(a[j]>=n){
          e=1;
          break;
        }
      }
      if(e==0){
        break;
      }
    }  
    printf("%lld\n", ans);
    return 0;
  }
	
	for(ll i=1; i<n; i++){
		ll d=(a[0]-a[i])/(n+1);
		for(ll j=0; j<i; j++){
			a[j]-=((n-i+1)*d);
		}
		for(ll j=i; j<n; j++){
			a[j]+=(i*d);
		}
		ans+=(i*d);
	}
  if(a[0]<=n-1){
    printf("%lld\n", ans);
    return 0;
  }
	if(a[0]>=2*n+10){
      ll d=a[0]-2*n-10;
      ans+=(d*n);
      
      for(ll i=0; i<n; i++){
        a[i]-=d;
      }
    }
    while(1){
      ll m=-1, im;
      for(ll j=0; j<n; j++){
        if(m<a[j]){
          m=a[j], im=j;
        }
      }
      for(ll i=0; i<n; i++){
        if(im==i){
          a[i]-=n;
        }else{
          a[i]++;
        }
      }
      ans++;
      bool e=0;
      for(ll j=0; j<n; j++){
        if(a[j]>=n){
          e=1;
          break;
        }
      }
      if(e==0){
        break;
      }
    }
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 384
while True:
  n, k = map(int, input().split())
  if n == 0 and k == 0:
    break
  a = [int(input()) for _ in range(n)]
  s = sum(a[0:k])
  ss = [s]
  for i in range(k, n):
    s = s + a[i] - a[i-k]
    ss.append(s)
  print(max(ss))


Measured memory_bytes: 11708
from itertools import product


def count(ss, ns, ps):
    for i, s in enumerate(ss):
        sum_s = sum([ns[_s - 1] for _s in s])
        if sum_s % 2 != ps[i]:
            return 0
    return 1


n, m = list(map(int, input().split(" ")))
ks = []
ss = []
for _ in range(m):
    k, *s = list(map(int, input().split(" ")))
    ks.append(k)
    ss.append(s)
ps = list(map(int, input().split(" ")))

ns_list = list(product([0, 1], repeat=n))
ans = 0
for ns in ns_list:
    ans += count(ss, ns, ps)
print(ans)


Measured memory_bytes: 3188
package main
 
import(
  "fmt"
	"bufio"
	"os"
	"strings"
)
 
var sc = bufio.NewScanner(os.Stdin)
 
func Rr() []string {
  sc.Scan()
  slice := strings.Split(sc.Text(), " ")
  return slice
}
 
func abc141b(S string){
	for i := 0;i<len(S);i++ {
		if i % 2 == 0{
			if S[i:i+1] == "L"{
				fmt.Println("No")
				break
			}
		}else{
			if S[i:i+1] == "R"{
				fmt.Println("No")
				break
			}
		}
		if i == len(S)-1{
			fmt.Println("Yes")
		}
	}
}	
 
func main(){
	x := ""
	fmt.Scan(&x)
	abc141b(x)
}

Measured memory_bytes: 640
#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<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pb push_back
#define N 300005
#define ll long long
#define int ll 
#define pi pair<int , int>
#define pip pair<pair ,int>
#define mp make_pair 
#define f first
#define s second
#define mod 998244353
ll Mod(ll x, ll y, int p) 
{ll res = 1; x = x % p;
while (y > 0) 
{if(y & 1) res = (res*x) % p; 
y = y>>1;x = (x*x) % p; 
}return res; 
}
int* getlps(string pattern){
 int len = pattern.length();
 int * lps = new int[len];
 lps[0] = 0;
 int i = 1 , j = 0;
 while(i < len){
  if(pattern[i] == pattern[j]){
	  lps[i] = j+1;
   i++;
   j++;
  }
  else{
		if(j != 0){
		 j = lps[j-1];
		}
		else{
		 lps[i] = 0;
		 i++;
		}
  }
 }
 return lps;
}
class Triplet{
 public:
 int x ;
 int y ;
 int gcd;
};
Triplet extendedEuclid(int a , int b){
 if(b == 0){Triplet ans; ans.gcd = a;ans.x = 1;ans.y = 0;return ans;}
 Triplet smallAns = extendedEuclid(b , a%b);
 Triplet ans;
 ans.gcd = smallAns.gcd;
 ans.x = smallAns.y;
 ans.y = smallAns.x - (a/b)*smallAns.y;
 return ans;
}
int mmInverse(int a , int m){
 Triplet ans = extendedEuclid(a , m);
 return ans.x;
}
int n;
int arr[N];
map<pi , int> dp;
const int MIN = -1e18;
int fun(int idx , int k){
   //if(idx >= n && k > 0)return MIN;
   //if(k == 0 && idx > n)return 0;
   if(k == 0)return 0;
   if(idx > n)return MIN;
    if(n-idx+1 < 2*k - 1)return MIN;
   if(dp.count({idx , k}) > 0)return dp[{idx , k}];
   //if(v[idx])return dp[idx];
  // v[idx] = true;
   int sum = 0;
  // if(k > 0){
     sum = arr[idx]+fun(idx+2 , k-1);
 //}
   int op2 = fun(idx+1 , k);
   return dp[{idx , k}] = max(sum , op2);
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(int i = 1 ; i <= n ; i++){
		cin>>arr[i];
}
//memset(v , false , sizeof(v));
cout<<fun(1 , n/2)<<endl;
}


Measured memory_bytes: 33292
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>

using namespace std;

void solve()
{
	unsigned long long int N, A, B;
	cin >> N >> A >> B;
	vector<unsigned long long int> X(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> X[i];
	}
	unsigned long long int ans = 0;
	int cur = X[0];
	for (int i = 1; i < N; ++i)
	{
		ans += min((X[i] - cur) * A, B);
		cur = X[i];
	}
	cout << ans << endl;
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF      100000000
#define EPS      1e-10
#define MOD      1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int k, t;
int a[100];

int main(){
    cin >> k >> t;
    int ma = 0;
    rep(i,t){
        cin >> a[i];
        ma = max(ma,a[i]);
    }
    if((k+1)/2 >= ma){
        cout << 0 << endl;
    } else{
        if(k%2 == 0) cout << (ma-(k+1)/2)*2-1 << endl;
        else cout << (ma-(k+1)/2) *2 << endl;
    }
}


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

int main() {
  double n, k; cin >> n >> k;
  int c = 1;
  double ans = 0;
  for (int i = n; i>0; i--) {
    while (i*c<k) {
      c*=2;
    }
    ans += 1.0 / (n*c);
  }
  cout << fixed << setprecision(10);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3760
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;
using namespace std;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
//     tree_order_statistics_node_update>;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
typedef long long int ll;
const ll N = 1e6;
// const ll m = 1e9 + 7;
// const ll inf= 1e14;
const ll mod = 998244353 ;
const ll INF = 1e16;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define pld pair<ld,ld>
#define pll pair<ll, ll>
#define pii pair<ll, ll>
#define ld long double
ll powm(ll a, ll b) { a = a%mod;ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
string a,b;
bool comp(ll i,ll j){
    return a[i]>a[j];
}
int main() {   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt","w",stderr);    
    #endif
    ll t = 1;
    // cin>>t; 
    while(t--){
        string s;cin>>s;
        for(auto i:s){
            if(i=='?'){
                cout<<'D';
            }
            else{
                cout<<i;
            }
        }
        cout<<'\n';
    }
}              

Measured memory_bytes: 3712
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
int a,b;string s;
int main()
{
  cin>>a>>b>>s;
  if(s[a]!='-'){cout<<"No"<<endl;return 0;}
  for(int i=0;i<a;i++)
    if(s[i]<'0'||s[i]>'9'){cout<<"No"<<endl;return 0;}
  for(int i=a+1;i<=a+b;i++)
    if(s[i]<'0'||s[i]>'9'){cout<<"No"<<endl;return 0;}
  cout<<"Yes"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
using namespace std;
const int N=2e5+5;
int n,p[N],mx,ct[N],ts,rt[N],an[2];
char ans[N];
struct nod{int l,r,mx[2];}t[N*19];
void qu(int v,int l,int r,int x){
	if(x<=l||!v){
		fo(o,0,1)an[o]=max(an[o],t[v].mx[o]);
		return;
	}
	int m=l+r>>1;
	if(x<=m){
		fo(o,0,1)an[o]=max(an[o],t[t[v].r].mx[o]);
		qu(t[v].l,l,m,x);
	}else qu(t[v].r,m+1,r,x);
}
void ch(int &v,int l,int r,int x){
	t[++ts]=t[v];v=ts;
	fo(o,0,1)t[v].mx[o]=max(t[v].mx[o],an[o]);
	if(l==r)return;
	int m=l+r>>1;
	if(x<=m)ch(t[v].l,l,m,x);else ch(t[v].r,m+1,r,x);
}
bool ck2(int cx,int cy,int hx,int hy,int i){
	int a=cx-cy+ct[i];
	if(a<0)return 0;
	an[0]=an[1]=0;
	if(hy<n)qu(rt[i],1,n,hy+1);
	return a<=an[a&1];
}
bool ck(int cx,int cy,int hx,int hy,int i){
	if(ck2(cx,cy,hx,hy,i)||ck2(cy,cx,hy,hx,i))return 1;
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	fo(i,1,n)cin>>p[i],(mx<p[i]?ct[i]=1,mx=p[i]:0);
	fd(i,1,n){
		rt[i]=rt[i+1];
		an[0]=an[1]=0;
		if(p[i]<n)qu(rt[i],1,n,p[i]+1);
		if(ct[i])an[0]+=2,an[1]+=2;
		else swap(an[0],an[1]),++an[0],++an[1];
		if(an[0]&1)an[0]=0;
		if(~an[1]&1)an[1]=0;
		ch(rt[i],1,n,p[i]);
		ct[i]+=ct[i+1];
	}
	int cx=0,cy=0,hx=0,hy=0;
	fo(i,1,n){
		if(ck(cx+(hx<p[i]),cy,max(hx,p[i]),hy,i+1)){
			if(p[i]>hx)++cx,hx=p[i];
			ans[i]='0';
			continue;
		}
		if(ck(cx,cy+(hy<p[i]),hx,max(hy,p[i]),i+1)){
			if(p[i]>hy)++cy,hy=p[i];
			ans[i]='1';
			continue;
		}
		return puts("-1"),0;
	}
	fo(i,1,n)putchar(ans[i]);
}

Measured memory_bytes: 62336
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
#define lP pair<ll, ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;

int N, H, W;

int main() {
	cin >> N >> H >> W;
	cout << (N - H + 1)*(N - W + 1) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
int main()
{
    ll n,k;
    cin>>n>>k;
    if(n>=k)
    {
        ll temp=n%k;
        ll ans=min(temp,k-temp);
        cout<<ans;
    }
    else
    {
        ll ans=min(n,k-n);
        cout<<ans;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int x, y, ans=0; cin>>x>>y;;
	if(x==1) ans+=300000;
	if(y==1) ans+=300000;
	if(x==2) ans+=200000;
	if(y==2) ans+=200000;
	if(x==3) ans+=100000;
	if(y==3) ans+=100000;
	if(x==1 && y==1) ans+=400000;
	cout<<ans<<endl;	
	return 0;
}

Measured memory_bytes: 256
while True:
  try:
    a_list = map(int, raw_input().strip().split(" "));
    b_list = map(int, raw_input().strip().split(" "));
  except:
    break;
  hit, blow = 0, 0
  for a, b in zip(a_list, b_list):
    if (a == b):
      hit += 1;
    elif(a in b_list):
      blow += 1;
  print hit, blow

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

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int[] X = new int[N];
            for (int i = 0; i < N; i++) {
                X[i] = in.nextInt();
            }

            int[] copy = Arrays.copyOf(X, N);
            Arrays.sort(copy);

            int l = copy[N / 2 - 1];
            int r = copy[N / 2];

            int[] medians = new int[N];
            for (int i = 0; i < N; i++) {
                if (X[i] <= l) {
                    medians[i] = r;
                } else {
                    medians[i] = l;
                }
            }

            for (int i = 0; i < N; i++) {
                System.out.println(medians[i]);
            }
        }
    }
}


Measured memory_bytes: 63532
import java.util.*;

public class Main {
 	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n + 1];
		for (int i = 1; i <= n; i++) {
		    arr[i] = sc.nextInt();
		}
		int l = sc.nextInt();
		int[][] dp = new int[18][n + 1];
		for (int i = 1; i <= n; i++) {
		    if (arr[n] - arr[i] <= l) {
		        dp[0][i] = n;
		        continue;
		    }
		    int left = i;
		    int right = n;
		    while (right - left > 1) {
		        int m = (left + right) / 2;
		        if (arr[m] - arr[i] == l) {
		            left = m;
		            break;
		        } else if (arr[m] - arr[i] < l) {
		            left = m;
		        } else {
		            right = m;
		        }
		    }
		    dp[0][i] = left;
		}
		for (int i = 1; i < 18; i++) {
		    for (int j = 1; j <= n; j++) {
		        dp[i][j] = dp[i - 1][dp[i - 1][j]];
		    }
		}
		int q = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    int start = Math.min(a, b);
		    int end = Math.max(a, b);
		    int days = 0;
		    for (int j = 17; j >= 0; j--) {
		        if (j == 0) {
		            if (dp[j][start] >= end) {
		                days++;
		                break;
		            } else {
		                days += 2;
		                break;
		            }
		        }
		        if (dp[j][start] < end) {
		            days += (int)Math.pow(2, j);
		            start = dp[j][start];
		        }
		    }
		    sb.append(days).append("\n");
		}
	    System.out.print(sb);
	}
}


Measured memory_bytes: 103532
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f (a:as) (b:bs) = x `seq` x : zipWith' f as bs
  where
    x = f a b
zipWith' _ _ _ = []

lucas :: [Int]
lucas = 2 : 1 : zipWith' (+) lucas (tail lucas)

main :: IO ()
main = readLn >>= print . (lucas !!)


Measured memory_bytes: 508
n = list(input())
 
a = []
b = []
for i in range(int((len(n)-1)/2)):
    a.append(n[i])
for i in range(int((len(n)+3)/2)-1,len(n)):
   b.append(n[i])
 
if a == b:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<vector<int> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    int n,k;
    cin >> n >> k;
    k--;n--;
    if(n%k==0){
        cout << n/k << endl;
    }
    else{
        cout << n/k+1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    int c=a-b;
    if(c<0){
        cout <<"a < b\n";
    }
    else if(c==0){
        cout<<"a == b\n";
    }
    else{
        cout <<"a > b\n";
    }
    
    return 0;
}


Measured memory_bytes: 3076
n = int(input())
line = list(map(int, input().split()))
total = 1
if 0 in line:
  print(0)
else:
  for i in range(n):
    total *= line[i]
    if total > 10 ** 18:
      break;
  if total > 10 ** 18:
    print(-1)
  else:
    print(total)

Measured memory_bytes: 21772
#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>


using namespace std;
using ll = long long int;

const ll MOD = 1000000007;

int main() {
  string S;
  cin >> S;
  ll N = S.length();

  vector<ll> as(N + 1), bs(N + 1), cs(N + 1);
  as[0] = 0;
  bs[0] = 0;
  cs[0] = 0;
  ll base = 1;

  for (int i = 0; i < N; i++) {
    if (S[i] == 'A') {
      as[i+1] = (as[i] + base) % MOD;
      bs[i+1] = bs[i];
      cs[i+1] = cs[i];
    } else if (S[i] == 'B') {
      as[i+1] = as[i];
      bs[i+1] = (bs[i] + as[i]) % MOD;
      cs[i+1] = cs[i];
    } else if (S[i] == 'C') {
      as[i+1] = as[i];
      bs[i+1] = bs[i];
      cs[i+1] = (cs[i] + bs[i]) % MOD;
    } else if (S[i] == '?') {
      as[i+1] = (3 * as[i] + base) % MOD;
      bs[i+1] = (3 * bs[i] + as[i]) % MOD;
      cs[i+1] = (3 * cs[i] + bs[i]) % MOD;
      base = (3 * base) % MOD;
    }
  }

  cout << cs[N] << endl;
  return 0;
}


Measured memory_bytes: 2880
s=input()
n1=len(s)
t=input()
n=len(t)
mini=int(1e9)
start=0
end=n-1
md=0
while end!=n1:
    md=0
    j=0
    for i in range(start,end+1,1):
        if s[i]!=t[j]:
            md+=1
        j+=1
    mini=min(mini,md)
    start+=1
    end+=1
print(mini)






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

void solve(std::istream &in, std::ostream &out);

int main() {
#ifdef LOCAL
  freopen("../IO/f.in", "r", stdin);
//  freopen("../IO/f.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  solve(std::cin, std::cout);
  return 0;
}

static constexpr int P = 988'244'353;
void solve(std::istream &in, std::ostream &out) {
  int n, k;
  in >> n >> k;
  vector<int> a(n);
  for (int &i : a) {
    in >> i;
  }
  int count = 0;
  vector<vector<int>> can_suff(n+1, vector<int>(k+1,0));
  vector<vector<int>> sum_suff(n+1, vector<int>(k+2,0));
  sum_suff[n] = vector<int>(k+2,1);
  can_suff[n][0] = 1;
  for (int i = n - 1; i >= 0; --i) {
    can_suff[i] = can_suff[i + 1];
    if (a[i] < k) {
      for (int w = k; w >= 0; --w) {
        can_suff[i][min(k, w + a[i])] |= can_suff[i][w];
      }
    }
    for (int w = 0; w <= k; ++w) {
      sum_suff[i][w + 1] = sum_suff[i][w] + can_suff[i][w];
    }
  }
  vector<int> can(k + 1, 0);
  can[0] = 1;
  for (int i = 0; i < n; ++i) {
    if (a[i] >= k) continue;
    bool found = false;
    int L = k - a[i], R = k; // [L, R)
    for (int j = L; j < R && !found; ++j) {
      if (can[j]) {
        found = true;
      }
    }
    for (int sum = 0; sum < L && !found; ++sum) {
      if (!can[sum]) continue;
      int ll = L - sum, rr = R - sum;
      if (sum_suff[i + 1][rr] - sum_suff[i + 1][ll] > 0) {
        found = true;
      }
    }
    for (int w = k; w >= 0; --w) {
      can[min(k, w + a[i])] |= can[w];
    }
    count += !found;
  }
  out << count;
}

Measured memory_bytes: 199096
#include <iostream>
#include <vector>
#include <utility>
#include <tuple>

using ll = long long;

ll height[51], meat[51];

void initialize() {
  height[0] = 1;
  meat[0] = 1;
  for (int i = 1; i <= 50; i++) {
    height[i] = height[i - 1] * 2 + 3;
    meat[i] = meat[i - 1] * 2 + 1;
  }
}

std::pair<ll, ll> eat(int level, ll size) {
  if (size >= height[level])
    return {meat[level], size - height[level]};
  if (size == 0 || size == 1)
    return {0, 0};
  ll meat1, rest1;
  std::tie(meat1, rest1) = eat(level - 1, size - 1);
  if (rest1 == 0)
    return {meat1, 0};
  if (rest1 == 1)
    return {meat1 + 1, 0};
  ll meat2, rest2;
  std::tie(meat2, rest2) = eat(level - 1, rest1 - 1);
  if (rest2 == 0)
    return {meat1 + meat2 + 1, 0};
  std::cerr << "cannot reach here" << std::endl;
  std::exit(1);
  return {-1, 0};
}

int main() {
  initialize();
  int n;
  ll x;
  std::cin >> n >> x;
  std::cout << eat(n, x).first << std::endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int r,c,i,j,x,y,z;

  scanf("%d %d",&r,&c);
  
  int a[101][101];

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

  (x=0);

  for(i=0;i<r;i++){
    for(j=0;j<c;j++){
      (x=x+a[i][j]);
      (a[i][c]=x);
    }
    (x=0);
  }

  (z=0);

  for(i=r;i<r+1;i++){
    for(j=0;j<c;j++){
      (z=z+a[i][j]);
      (a[r][c]=z);
    }
    (z=0);
  }

  for(i=0;i<r+1;i++){
    for(j=0;j<c+1;j++){
      printf("%d",a[i][j]);
      if(j<c){
	printf(" ");
      }
    }
    printf("\n");
   }
  return 0;
}

  

Measured memory_bytes: 1072
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;

const int N=105;

int p1,p2,m;
ll n;
int a[N],b[N];

int main(){
	int i;
	scanf("%lld",&n); n++;
	p1=p2=0; m=100;
	while (n>1){
		if (n&1ll) a[++p1]=m--,n--;
		else b[++p2]=m--,n>>=1;
	}
	printf("%d\n",(p1+p2)*2);
	for (i=1;i<=p1;i++) printf("%d ",a[i]);
	for (i=p2;i>=1;i--) printf("%d ",b[i]);
	for (i=1;i<=(p1+p2);i++) printf("%d ",m+i);
	return 0;
}

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

bool isPrime(int x){
    int i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

int main(){
    ll n;
    cin>>n;
    while(1){
        if(isPrime(n)){
            break;
        }
        n++;
    }
    cout<<n;
}

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

class Code{
	static void Main(string[] args){
    	Method(args);
        Console.WriteLine();
    }
    
    static void Method(string[] args){
        int n=int.Parse(Console.ReadLine());
        var vs = new int[n];
        string[] s=Console.ReadLine().Split(' ');
        for(int i=0;i<n;i++){
        	vs[i] = int.Parse(s[i]);
        }
      
    	var evens = new int[100000];
    	var odds = new int[100000];
      	for(int i=0;i<n;i++){
          if(i%2==0){
            odds[vs[i]-1]++;
          }
          else{
            evens[vs[i]-1]++;            
          }
        }
      int evenMax=-1,evenSub=0;
      int oddMax=-1,oddSub=0;
      if(evens[0]<evens[1]){
        evenMax=1;
        evenSub=0;
      }
      else{
        evenMax=0;
        evenSub=1;
      }
      if(odds[0]<odds[1]){
        oddMax=1;
        oddSub=0;
      }
      else{
        oddMax=0;
        oddSub=1;
      }
      
      for(int i=2;i<100000;i++){
        if(evens[evenMax]<evens[i]){
          evenSub=evenMax;
          evenMax = i;
        }
        else if(evens[evenSub]<evens[i]){
          evenSub=i;
        }
        if(odds[oddMax]<odds[i]){
          oddSub=oddMax;
          oddMax = i;
        }
        else if(odds[oddSub]<odds[i]){
          oddSub=i;
        }
      }
      /*Console.WriteLine(evenMax);
      Console.WriteLine(evenSub);
      Console.WriteLine(oddMax);
      Console.WriteLine(oddSub);*/
      if(evenMax!=oddMax){
        Console.WriteLine(n-evens[evenMax]-odds[oddMax]);
      }
      else{
        if(evens[evenMax]+odds[oddSub]<evens[evenSub]+odds[oddMax]){
          Console.WriteLine(n-evens[evenSub]-odds[oddMax]);
        }
        else{
          Console.WriteLine(n-evens[evenMax]-odds[oddSub]);          
        }
      }
    }
}

Measured memory_bytes: 19680
N = int(input())
a = [int(input()) for _ in range(N)]

i = 0
m = 1
while(1):
    if a[i] == 2:
        ans = m
        break

    if m >= N:
        ans = -1
        break

    i = a[i] - 1 
    m += 1

print(ans)

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

int main(){
    int a,b,n=0;string s;cin>>a>>b>>s;
    for(int i=0;i<a+b+1;i++){
        if(s.at(i)=='-') n++;
    }
    if(s.at(a)=='-'&&n==1) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long K;
  cin >> K;
  vector<long long> a(50, K / 50 + 49);
  for (int i = 0; i < K % 50; i++){
    for (int j = 0; j < 50; j++){
      if (i == j){
        a[j] += 50;
      } else {
        a[j]--;
      }
    }
  }
  cout << 50 << endl;
  for (int i = 0; i < 50; i++){
    cout << a[i];
    if (i < 49){
      cout << ' ';
    }
  }
  cout << endl;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N, a, point=0;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>a;
        if(a%2==0){
            point+=1;
        }
    }
    cout<<point<<endl;
}



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

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

 int main() {
   int N, M;
   string ans = "IMPOSSIBLE";
   cin >> N >> M;
   vector<bool> r1(N + 1), rN(N + 1);
   rep(i, M) {
     int tmp1, tmp2;
     cin >> tmp1 >> tmp2;
     if (tmp1 == 1) r1.at(tmp2) = true;
     if (tmp2 == N) rN.at(tmp1) = true;
   }

   for (int i = 1; i <= N; i++) {
     if (r1.at(i) == true) {
       if (rN.at(i) == true) {
         ans = "POSSIBLE";
         break;
       }
     }
   }

   cout << ans << endl;
 }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[105][105]; 
int main()
{
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=m;i++)
	{
		bool ok=true;
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]=='#')
			{
				ok=false;
				break;
			}
		}
		if(ok==true)
		{
			for(int j=i+1;j<=m;j++)
			{
				for(int k=1;k<=n;k++)
				{
					a[j-1][k]=a[j][k];
				}
			}
			i--;
			m--;
		}
	}
///	cout<<m<<n<<endl;
//	for(int i=1;i<=m;i++)
//	{
//		for(int j=1;j<=n;j++)
//		{
//			cout<<a[i][j];
//		}
//		cout<<"\n";
//	}
	for(int i=1;i<=n;i++)
	{
		bool ok=true;
		for(int j=1;j<=m;j++)
		{
			if(a[j][i]=='#')
			{
				ok=false;
				break;
			}
		}
		if(ok==true)
		{
			for(int j=1;j<=m;j++)
			{
				for(int k=i+1;k<=n;k++)
				{
					a[j][k-1]=a[j][k];
				}
			}
			i--;
			n--;
		}
	}
//	cout<<m<<n<<endl;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<a[i][j];
		}
		cout<<"\n";
	}
	return 0;
}


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


int lb(vi &min, int &g, int a, int b) {
    if(b-a == 1) {
        return b;
    }
    int c = (a+b)/2;
    if(min[c] >= g) {
        a = c;
    } else {
        b = c;
    }
    return lb(min, g, a, b);
}

 
int main() {
    int n;
    cin >> n;
    vector<int> min(1);
    min[0] = 1000000001;
    int ans = 0;
    rep(i, n) {
        int g;
        cin >> g;
        if(min[min.size()-1] >= g) {
            ++ans;
            min.push_back(g);

        } else {
            int num = lb(min, g, 0, min.size());
            min[num] = g;
        }
        
    }

    cout << ans << endl;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

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

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

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

  rep(i, 3) {
    if (n[i] == '1')
      cout << 9;
    else
      cout << 1;
  }
  cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
static const int64_t mod=1000000007;
int64_t N,A,B;
int64_t dp[4][200005];
int64_t sum[2][200005];
int main(){
  cin>>N>>A>>B;
  vector<int64_t>S(N+1);
  S[0]=-1000000000000000001;
  for(int i=1;i<=N;i++)
    cin>>S.at(i);
  set<int64_t>SA;set<int64_t>SB;
  for(int i=0;i<N-1;i++){
    if(S[i+1]-S[i]<A)
      SA.insert(i);
    if(S[i+1]-S[i]<B)
      SB.insert(i);
  }vector<int64_t>a(N+1);
  vector<int64_t>b(N+1);
  for(int i=1;i<=N;i++){
  auto itra=upper_bound(S.begin(),S.end(),S.at(i)-A);
     auto itrb=upper_bound(S.begin(),S.end(),S.at(i)-B);
    int64_t k1=distance(S.begin(),itra);
    int64_t k2=distance(S.begin(),itrb);
    a[i]=k1;
    b[i]=k2;
     }dp[0][1]=1;dp[1][1]=1;
       sum[0][1]=1;sum[1][1]=1;
  int64_t a1=0;int64_t b1=0;
  for(int i=2;i<=N;i++){
  if(a[i]==i){
  dp[2][i]=(dp[0][i-1]+dp[2][i-1])%mod;
    dp[0][i]=(sum[1][i-1]-sum[1][b1])%mod;sum[0][i]=(sum[0][i-1]+dp[0][i])%mod;
  }else{
  if(b1<a[i])
    dp[0][i]=(sum[1][a[i]]-sum[1][b1])%mod;sum[0][i]=(sum[0][i-1]+dp[0][i])%mod;
  }
  if(b[i]==i){
  dp[3][i]=(dp[1][i-1]+dp[3][i-1])%mod;
    dp[1][i]=(sum[0][i-1]-sum[0][a1])%mod;sum[1][i]=(sum[1][i-1]+dp[1][i])%mod;
  }else{
   if(a1<b[i])
    dp[1][i]=(sum[0][b[i]]-sum[0][a1])%mod;sum[1][i]=(sum[1][i-1]+dp[1][i])%mod;
  }if(SA.count(i-1))
    a1=i-1;
    if(SB.count(i-1))
      b1=i-1;
   }int64_t ans=(dp[0][N]+dp[1][N]+dp[2][N]+dp[3][N])%mod;
  ans=(ans+mod)%mod;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 19596
#include<stdio.h>
int main(void)
{
	char ch;
	
	while(1)
	{
		scanf("%c",&ch);
		
		if(ch>=65 && ch<=90)
		{
			ch+=32;
		}
		else if(ch>=97 && ch<=122)
		{
			ch-=32;
		}
		
		printf("%c",ch);
		
				if(ch == '\n')
		{
			break;
		}
	}
	
	return 0;
}


Measured memory_bytes: 2072
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = list(input())[:-1]
n = len(N)
b = 0
for i in range(n):
    s = N[i]
    a = int(s)
    b += a
    b %= 9
if b % 9 == 0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 13156
S = input()
N = len(S)

if S == "keyence":
    print("YES")
    exit()

for i in range(N):
    for j in range(i, N):
        s = S[:i] + S[j + 1:]
        # print(s)
        if s == "keyence":
            print("YES")
            exit()

print("NO")


Measured memory_bytes: 2940
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;
constexpr long long int INF = std::numeric_limits<long long int>::max();
constexpr long long int NINF = std::numeric_limits<long long int>::min();
#define int long long int

int sum(const vector<int> &q, int N) {
  int ret = 0;
  for (int i = 0; i < N && i < q.size(); i++) {
    ret += q[i];
  }
  return ret;
}

void solve() {
  int N, K;
  cin >> N >> K;

  vector<int> V(N + 2, 0);
  for (int i = 1; i <= N; i++) {
    cin >> V[i];
  }

  vector<int> A = V;
  vector<int> B = V;
  reverse(B.begin(), B.end());

  int ans = NINF;
  int cl = 0;
  vector<int> vl;
  for (int l = 0; l <= N; l++) {
    cl += A[l];
    if (A[l] < 0) {
      vl.push_back(A[l]);
    }

    int cost = cl;
    vector<int> v = vl;
    for (int r = 0; r <= N - l && l + r <= K; r++) {
      cost += B[r];
      if (B[r] < 0) {
        v.push_back(B[r]);
      }

      sort(v.begin(), v.end());
      ans = max(ans, cost - sum(v, K - l - r));
    }
  }
  cout << ans << endl;
}

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


Measured memory_bytes: 256
module Main where

import Control.Applicative

getInt :: IO Int
getInt = head <$> getInts

getInts :: IO [Int]
getInts = map read . words <$> getLine

main :: IO ()
main = do
  { [a, b, c] <- getInts
  ; if a < b then if b < c then putStrLn "Yes"
                  else putStrLn "No"
    else putStrLn "No"
  }



Measured memory_bytes: 3592
fun main(args: Array<String>) {
    val n= readLine()!!.toInt()
    val a= readLine()!!.split(" ").map{it.toLong()}
            .groupBy { it }.mapValues { it.value.size }
            .filterValues { it>=2 }
            .toList().sortedByDescending { it.first }

    val h=a.getOrElse(0){0L to 0}
    val w= if(h.second>=4) h
    else a.getOrElse(1){0L to 0}
            
    println(h.first * w.first)
}

Measured memory_bytes: 80868
import java.io.IOException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);

		double r = sc.nextDouble();
		double p = Math.PI;

		String x = String.format("%.8f",(Math.pow(r, 2)*p));
		String y = String.format("%.8f",((2*r)*p));

		System.out.println(x + " " + y);

		sc.close();
	}
}


Measured memory_bytes: 28204
import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = bisect.bisect(l, l[i]+l[j]-1)
        ans += (a-j-1)
print(ans)

Measured memory_bytes: 9292
// ref: https://img.atcoder.jp/abc099/editorial.pdf
// ref: https://qiita.com/drken/items/ace3142967c4f01d42e9

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;
using namespace std;

//---

template <typename T>
inline void print(const T& rhs){ std::cout<<" = "<<rhs<<std::endl; }
template <typename T>
inline void print(const std::vector<T>& rhs){
    std::cout<<" = [ ";
    for(uint i=0; i<rhs.size(); ++i){ std::cout<<rhs[i]<<' '; }
    std::cout<<"]"<<std::endl;
}
template <typename T>
inline void print(const std::vector<std::vector<T>>& rhs){
    std::cout<<" = "<<std::endl;
    std::cout<<"[[ ";
    for(uint p=0; p<rhs.size(); ++p){
        if(p!=0){ std::cout<<" [ "; }
        for(uint q=0; q<rhs[p].size(); ++q){
            std::cout<<rhs[p][q]<<' ';
        }
        if(p!=rhs.size()-1){ std::cout<<"]"<<std::endl; }
    }
    std::cout<<"]]"<<std::endl;
}
template <typename TL, typename TR>
inline void print(const std::vector<std::pair<TR,TL>>& rhs){
    std::cout<<" = [";
    uint i=0;
    for(; i<rhs.size()-1; ++i){ std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"], "; }
    std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"]]" << endl;
}
#define printn(var) {printf("%s", #var);print(var);}
#define printn_all(var) {printf("%s(%d): ", __func__, __LINE__);printf("%s", #var);print(var);}

//---

int NNumber_digitSum(int val, int nNum){
    int ret=0;
    while(val > 0){
        ret += val % nNum;
        val /= nNum;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N; cin >> N;
    
    int steps=INT_MAX;
    for(int i=0; i<=N; ++i){
        int tmp = NNumber_digitSum(i, 6) + NNumber_digitSum(N-i, 9);
        steps = min(steps, tmp);
    }
    cout << steps << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

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

#define MP make_pair
#define EACH(i,c) for(auto i: c)
#define SORT(c) sort((c).begin(),(c).end())

#define ALL(a)  (a).begin(),(a).end()

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

	int A[3][3];
	REP(i, 3) REP(j, 3) cin >> A[i][j];

	int N;
	cin >> N;

	int B[3][3] = {0};
	REP(_, N){
		int b;
		cin >> b;
		REP(i, 3) REP(j, 3){
			if(A[i][j] == b) B[i][j] = 1;
		}
	}

	bool ret = false;
	REP(i, 3){
		bool ok = true;
		REP(j, 3) if(B[i][j] == 0) ok = false;
		ret |= ok;
	}
	REP(j, 3){
		bool ok = true;
		REP(i, 3) if(B[i][j] == 0) ok = false;
		ret |= ok;
	}
	{
		bool ok = true;
		REP(i, 3){
			if(B[i][i] == 0) ok = false;
		}
		ret |= ok;
	}
	{
		bool ok = true;
		REP(i, 3){
			if(B[2 - i][i] == 0) ok = false;
		}
		ret |= ok;
	}

	cout << (ret ? "Yes" : "No") << endl;
	return 0;
}


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

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

  char A[110];
  char B[110];
  for (int i = 0; i < 110; i++) {
    A[i] = 0;
    B[i] = 0;
  }
  scanf("%s", A);
  scanf("%s", B);

  int a = 0;
  if (strlen(A) > strlen(B)) {
    printf("GREATER\n");
  }else if(strlen(A) < strlen(B)) {
    printf("LESS\n");
  }else if(strlen(A) == strlen(B)) {
    int i;
    for (i = 0; i < strlen(A); i++) {
      //printf("%d桁目\n", i);
      if (A[i] > B[i]) {
        printf("GREATER\n");
        return 0;
      }else if(A[i] < B[i]){
        printf("LESS\n");
        return 0;
      }
    }
    printf("EQUAL\n");
  }

  return 0;
}


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

const int MAXN=3005;
long long dp[MAXN][MAXN];
int arr[MAXN];

long long solve(int i,int j)
{
    if(dp[i][j]!=-1)
    return dp[i][j];
    if(i==j)
    return dp[i][j]=arr[i];
    dp[i][j]=max(arr[i]-solve(i+1,j),arr[j]-solve(i,j-1));
    return dp[i][j];
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>arr[i];
    long long y=solve(1,n);
    cout<<y<<"\n";
}


Measured memory_bytes: 71040
n,m = map(int,input().split())
l = [0] *m
r = [0] *m

for i in range(m):
    li,ri = map(int,input().split())
    l[i] = li
    r[i] = ri
lm = max(l)
rm = min(r)
print(max(0,rm-lm+1))

Measured memory_bytes: 45400
#include <stdio.h>

int main(){
	int i,class[30],n,notcheck[2];
	for(i=0;i<30;i++){
		class[i] = 0;
	}
	for(i=0;i<28;i++){
		scanf("%d",&n);
		class[n-1] = 1;
	}
	n = 0;
	for(i=0;i<30;i++){
		if(class[i] == 0){
			notcheck[n] = i+1;
			n += 1;
		}
	}
	printf("%d\n%d\n",notcheck[0],notcheck[1]);
	return 0;
}

Measured memory_bytes: 0