akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, d, a = LI()
X = []
H = []
xh = LIR(n)
xh.sort()
for x, h in xh:
    X += [x]
    H += [h]

X2 = [0] * n
ret = 0
ans = 0
for i in range(n):
    x = X[i]
    ret -= X2[i]
    remain = H[i] - ret
    if remain > 0:
        j = remain // a + bool(remain % a)
        ans += j
        ret += j * a
        if x + d * 2 < X[-1]:
            l = i
            r = n
            while l + 1 < r:
                mid = (l + r) // 2
                if X[mid] <= x + d * 2:
                    l = mid
                else:
                    r = mid
            X2[r] += j * a


print(ans)

Measured memory_bytes: 92508
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] hw = Console.ReadLine().Split(' ');
            int H = int.Parse(hw[0]);
            int W = int.Parse(hw[1]);
            string[] hw2 = Console.ReadLine().Split(' ');
            int h2 = int.Parse(hw2[0]);
            int w2 = int.Parse(hw2[1]);
            int ans = (H - h2) * (W - w2);
            Console.WriteLine(ans);

        }
    }
}


Measured memory_bytes: 11092
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Dont keep array name as size or any other key word

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007 //998244353
#define lld long double
#define mii map<int, int>
#define mci map<char, int>
#define msi map<string, int>
#define pii pair<int, int>
#define ff first
#define ss second 
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)    
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const long long N=1000005, INF=2000000000000000000;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
    int g=__gcd(a, b);
    return a/g*b;
}
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(res*a)%p;
            b>>=1;
            a=(a*a)%p;
        }
        return res;
    }
int sp[N];
bool vis[N];
int32_t main()
{
    IOS;
    fill(vis, false);
    for(int i=1;i<N;i++)
    sp[i]=i;
    for(int i=2;i<N;i++)
    {
        if(sp[i]==i)
        {
            for(int j=(i*i);j<N;j+=i)
            {
                if(sp[j]==j)
                sp[j]=i;
            }
        }
    }
    int n;
    cin>>n;
    int ar[n];
    for(int i=0;i<n;i++)
    cin>>ar[i];
    int f=0;
    int g=0;
    for(int i=0;i<n;i++)
    {
        g=__gcd(ar[i], g);
        while(ar[i]!=1)
        {
            int d=sp[ar[i]];
            while(ar[i]%d==0)
            ar[i]/=d;
            if(vis[d])
            f=1;
            vis[d]=true;
        }
    }
    if(f==0)
    cout<<"pairwise coprime";
    else if(g==1)
    cout<<"setwise coprime";
    else
    cout<<"not coprime";
}

Measured memory_bytes: 20200
#include <cstdio>

int f[2001][2001],n,k,invmul[4000001],_mul[4000001];
const int P=1000000007;
inline int mul(const int &a,const int &b){return 1ll*a*b%P;}
inline int add(int a,const int &b){a+=b;return(a>=P)?a-P:a;}
inline int sub(int a,const int &b){a-=b;return (a<0)?a+P:a;}
inline int C(const int &n,const int &m){return mul(mul(_mul[n],invmul[m]),invmul[n-m]);}
int main(){
	scanf("%d%d",&n,&k);
	if(k==1){
		puts("1");
		return 0;
	}
	_mul[0]=_mul[1]=invmul[0]=invmul[1]=1;
	for(int i=2;i<=n*k;i++)_mul[i]=mul(_mul[i-1],i);
	for(int i=2;i<=n*k;i++)invmul[i]=mul(P-P/i,invmul[P%i]);
	for(int i=2;i<=n*k;i++)invmul[i]=mul(invmul[i-1],invmul[i]);
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		f[i][0]=1;
		for(int j=1;j<=i;j++)
			f[i][j]=add((j<i)?f[i-1][j]:0,mul(f[i][j-1],C(n*k-i-(j-1)*(k-1)-1,k-2)));
	}
	printf("%d ",mul(f[n][n],_mul[n]));
}

Measured memory_bytes: 47104
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String s = "";
        for (int i=0; i<k; i++) {
            s += "ACL";
        }
        System.out.print(s);
    }			    
}


Measured memory_bytes: 38584
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <ctime>
#include <random>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define eps 1e-9
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;

int main() {
	speed;
	int n;
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; ++i)
		cin >> v[i];
	int ans = 0;
	for (int a = 0; a < n; ++a)
		for (int b = a + 1; b < n; ++b)
			for (int c = b + 1; c < n; ++c)
				if (v[a] != v[b] && v[b] != v[c] &&
					v[a] != v[c] && v[a] + v[b] > v[c] && v[c] + v[b] > v[a] && v[a] + v[c] > v[b])
					ans++;
	cout << ans;
}

Measured memory_bytes: 3192
/*************************************************************************
	> File Name: abc120_b.cpp
	> Author: 
	> Mail: 
	> Created Time: 2019年03月03日 星期日 20时07分55秒
 ************************************************************************/

#include<iostream>
using namespace std;
int main()
{
    int a,b;int k;int aa[10010];
    cin>>a>>b;
    cin>>k;int num=0;
    for(int i=1;i<=100;i++)
    {
          if(i>a||i>b)break;
        if((a%i)==0&&(b%i)==0)
         { aa[num++]=i;
      //   cout<<i<<endl;    
       }
    }           
     cout<<aa[num-k]<<endl;
} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define PI 3.14159265358979323846
int main(void) {
    double A, B , H , M;
    double ans;
    cin >> A >> B >> H >> M;

    double ang_A,ang_B;
/*
    if(H>6)      ang_A = 30.0*(H-12);
    else         ang_A = 30.0*(H);

    if(M>30){     ang_B = 6.0*(M-60);
                ang_A += 0.5 * (M);
              }
    else      {   ang_B = 6.0*(M);
      ang_A += 0.5*M;
    }
*/
    ang_A = 30.0*H + 0.5*M;
    ang_B = 6.0*M;

    if(H==0 && M==0) {
      cout << abs(A-B) << endl;
      return 0;
    }

    ans = sqrt(A*A + B*B - 2.0*A*B*cos((ang_A-ang_B)*  PI/180.0));

    printf("%.10lf\n",ans );

    return 0;
}


Measured memory_bytes: 4112
#include <stdio.h>
#include <vector>
#include <list>
#include <map>
#include <array>
#include <memory>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <stdexcept>


using std::string;
using std::vector;


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// util
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

std::vector<std::string> split(const std::string& input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// user func
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void printList(const vector<int>& list) {
    // print
    for(int i = 0; i < list.size(); i++){
        printf(" %d", list[i]);
    }
    printf("\n");
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// logic
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Longest Common Subsequence
int LCS(const string& x, const string& y) {
    int result = 0;
    vector<vector<int>> table(x.length() + 1, vector<int>(y.length() + 1, 0));
    
    for (int i = 1; i <= x.length(); i++) {
        for (int j = 1; j <= y.length(); j++) {
            if (x[i-1] == y[j-1]) {
                table[i][j] += table[i-1][j-1] + 1;
            } else {
                table[i][j] = std::max(table[i-1][j], table[i][j-1]);
            }
            result = std::max(result, table[i][j]);
        }
    }
    return result;
}

void solve() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        char bufX[1024];
        char bufY[1024];
        scanf("%s", bufX);
        scanf("%s", bufY);
        printf("%d\n", LCS(string(bufX), string(bufY)));
    }
}


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


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

struct Node{
  int key;
  struct Node *right,*left,*parent;
};

struct Node *root,*NIL;

struct Node * treeMinimum(struct Node *x){
  while(x->left != NIL) x=x->left;
  return x;
}

struct Node * find(struct Node *u,int k){
  while(u!=NIL && k!= u->key){
    if(k<u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

struct Node * treeSuccessor(struct Node *x){
  if(x->right != NIL) return treeMinimum(x->right);
  struct Node *y = x->parent;
  while(y != NIL && x == y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

void treeDelete(struct Node *z){
  struct Node *x;
  struct Node *y;

  //削除する接点を決める
  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);

  //yの子xを決める
  if(y->left!=NIL){
    x = y->left;
  }else{
    x = y->right;
  }

  if(x !=NIL){
    x->parent = y->parent;
  }

  if(y->parent == NIL){
    root = x;
  }else{
    if(y == y->parent->left){
      y->parent->left = x;
    }else{
      y->parent->right = x;
    }
  }

  if(y!=z){
    z->key = y->key;
  }

  free(y);
}




void insert(int k){
  struct Node *y = NIL;
  struct Node *x = root;
  struct Node *z;

  z = (struct Node *)malloc(sizeof(struct Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key){
      x = x->left;
    }else{
      x = x->right;
    }
  }
  z->parent = y;
  if(y == NIL){
    root = z;
  }else{
    if(z->key < y->key){
      y->left = z;
    }else{
      y->right = z;
    }
  }
}


void inorder(struct Node *u){
  if(u == NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(struct Node *u){
  if(u == NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}
int main(){
  int n,i,x;
  char com[10];

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",com);
    if(com[0] == 'f'){
      scanf("%d",&x);
      struct Node *t = find(root,x);
      if(t != NIL) printf("yes\n");
      else printf("no\n");
    }else if(com[0] == 'i'){
      scanf("%d",&x);
      insert(x);
    }else if(com[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }else if(com[0] == 'd'){
      scanf("%d",&x);
      treeDelete(find(root,x));
    }
  }

  return 0;
}



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

int main() {
  int N;
  cin >> N;
  vector<vector<int>> A(2, vector<int>(N));
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < N; j++) {
      cin >> A[i][j];
    } 
  }
  int sum = 0, ans = 0;
  for (int i = 0; i < N; i++) {
    for (int k = 0; k <= i; k++) {
      sum += A[0][k];
      // cout << sum << endl;
    }
    for (int j = N - (N - i); j < N; j++) {
      sum += A[1][j];
      // cout << sum << endl;
    } 
    cout << endl;
    if (sum > ans) ans = sum;
    sum = 0;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3604
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N=sc.nextInt();

List<Integer> c = new ArrayList<Integer>();
int count = 0;

for(int i = 0; i<N; i++) {
	c.add(sc.nextInt());

}
	for(int i = 0; i< c.size(); i++) {
	      int x = c.get(i);
		while(x  % 2 == 0) {
			x/=2;
			count++;
		}
	}
System.out.println(count);
}
}

Measured memory_bytes: 35816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define int ll
//const ll mod = 1000000007;

string s;
int cnt,ans;

signed main() {
    cin >> s;
    const string agct = "AGCT";
    for (auto it = begin(agct); it != end(agct); it++) {
        replace(s.begin(), s.end(), *it, '#');
        // cout << s << endl;
    }

    for (auto it = begin(s); it != end(s); it++) {
        if(*it == '#') cnt++;
        else cnt = 0;
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound, __gcd, count, find, next_permutation
#include <bitset>    // bitset
#include <deque>     // deque
#include <iomanip>   // setprecsion
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <utility>   // pair, make_pair
#include <vector>    // vector

#include <cassert> // assert
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>  // abs, sin, cos, tan
#include <ctime> // clock

// __builtin_popcountll

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

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ld, ll, ll>> vtll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

void Main()
{
  ll a, b, x; cin >> a >> b >> x;
  ll ans = b / x - a / x;
  if(a % x == 0) ans++;
  fin(ans);
  return;
}

//前処理
int main()
{
  int ti = clock();
  srand((unsigned)time(NULL));
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  //cout << setfill('0') << internal << setw(4); //0埋め４桁
  Main();
  //cout << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl; // 実行時間計測
  return 0;
}

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

using namespace std;

long long powmod(long long a, long long b, long long m)
{
    long long r = 1;
    for (; b>0; b>>=1, a=a*a%m)
        if (b&1)
            r = r*a%m;
    return r;
}

int main()
{
    int N, A, B;
    long long K;
    cin>>N>>A>>B>>K;
    long long M = 998244353LL;
    vector<long long> P(N+1);
    P[0] = 1;
    for (int i=1; i<=N; i++)
        P[i] = i*P[i-1]%M;
    vector<long long> D(N+1);
    for (int i=0; i<=N; i++)
        D[i] = powmod(P[i], M-2, M);
    long long ans = 0;
    for (int a=0; a<=N; a++)
    {
        int b = (K - (long long)A*a)/B;
        if (0<=b && b<=N && (long long)a*A+(long long)b*B==K)
            ans += P[N]*D[a]%M*D[N-a]%M*P[N]%M*D[b]%M*D[N-b]%M,
            ans %= M;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using vc=vector<char>;
using vvc=vector<vc>;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

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

ll power(ll a, int b) {
  if(!b) return 1;
  ll c = power(a, b/2);
  if(b%2) return c*c%INF*a%INF;
  return c*c%INF;
}

int main() {
  int N;
  cin >> N;
  vi A(N);
  rep(i,N) cin >> A[i];
  ll ss=0,s=0;
  rep(i,N) {
    (ss+=(ll)A[i]*A[i])%=INF;
    (s+=(ll)A[i])%=INF;
  }
  
  cout << (s*s-ss+INF)%INF*power(2,INF-2)%INF << endl;
}

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

int main()
{
	string N;
	cin >> N;
	
	int digitSum = 0;
	for(int i = 0; i < (int)(N.length()); i++)
		digitSum += (N[i] - '0');
		
	if(digitSum % 9 == 0)
		printf("Yes");
		
	else
		printf("No");
}


Measured memory_bytes: 3820
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))

ans = 1000000000000000000
prod = 1
f = 0
f2 = 0

for i in range(n):
    if a[i] == 0:
        f = 1
        break

for i in range(n):
    prod = prod * a[i]

    if prod > ans:
        f2 = 1
        break

if f == 1:
    print(0)

else:
    if f2 == 1:
        print(-1)
    else:
        print(prod)
    

Measured memory_bytes: 82960
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define LONG 6378.1
#define PI 3.1415926535897932384626433832795

double xa,ya,xb,yb,l1,l2;

double anglediff(double a,double b){
	double dif=a-b;
	if(dif>360)dif-=360;
	if(dif<0)dif+=360;
	return dif;
}

int main(){
	while(scanf("%lf %lf %lf %lf",&xa,&ya,&xb,&yb)){
		if(ya<0)break;

		xa=xa*PI/180;
		ya=ya*PI/180;
		xb=xb*PI/180;
		yb=yb*PI/180;

		printf("%.0lf\n",floor(LONG*acos(sin(xa)*sin(xb)+cos(xa)*cos(xb)*cos(ya-yb))+0.5));

	}
	return 0;
}

Measured memory_bytes: 712
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n, k;
	int i;
	int cnt = 0;
	int input;
	vector<pair<int, int>> arr;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf("%d", &input);

		arr.push_back(make_pair(input, i));
	}

	sort(arr.begin(), arr.end());

	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i].second + 1);
	}

	return 0;
}

Measured memory_bytes: 1780
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(abs(a-c)<=d){
		cout<<"Yes";
	}
	else if(abs(a-c)>d&&abs(a-b)<=d&&
	abs(b-c)<=d){
		cout<<"Yes";
	}
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
d, g = gets.chomp.split(" ").map(&:to_i)

pt = []
ct = []

d.times do
  p_, c = gets.chomp.split(" ").map(&:to_i)
  pt << p_
  ct << c
end

ans = []

(1 << d).times do |mask|
  score = 0
  n = 0
  ires = 0
  d.times do |i|
    if ((mask >> i) & 1) == 1
      score += 100 * (i + 1) * pt[i] + ct[i]
      n += pt[i]
    else
      ires = i
    end
  end
  if score < g
    s = 100 * (ires + 1)
    need = (g - score + s - 1) / s
    if need >= pt[ires]
      next
    end
    n += need
  end
  ans << n
end
puts ans.min


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

#define mp make_pair

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;
typedef pair<int,int> pii;
typedef pair<i64,int> pli;
typedef pair<int,i64> pil;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;

template <typename T>
T id(T b) {return b;};
template <class It>
bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It>
bool any(It f,It l){return std::any_of(f,l,id<bool>);}

string s_, t;

int main()
{
  cin >> s_ >> t;
  set<string> c;
  for (int i = 0; i < int(s_.length()) && i+t.length() <= s_.length(); i++) {
    string s(s_);
    bool ok = true;
    for (int j = 0; j < int(s.length()) && ok; j++) {
      if (i <= j && j < int(i+t.length())) {
        if (s[j] == '?') s[j] = t[j-i];
        else if (s[j] != t[j-i]) ok = false;
      } else {
        if (s[j] == '?') s[j] = 'a';
      }
    }
    if (ok) c.insert(s);
  }

  if (!c.empty())
    cout << *c.begin() << endl;
  else
    cout << "UNRESTORABLE" << endl;

  return 0;
}


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

int main() {
  // 科目の数Nを受け取る
  int N,x=0,y=0,z=0,zz=0;
  char a;
  cin >> N;

  for(int i=0;i <N;i++)
  {
    cin >> a;
  //}
  //for (int l=0;l <N;l++)
  //{
    if(a=='G')
    {
      x++;
    }
    else if(a=='W')
    {
      y++;
    }
    else if(a=='P')
    {
      z++;
    }
    else if(a=='Y')
    {
      zz++;
    }

  }
  if(x!=0 &&y!=0&&z!=0&&zz!=0)
  {
    cout<< "Four"<<endl;
  }
  else 
  {
    cout<< "Three"<<endl;
  }


  





    return 0;
  
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <deque>
#include <list>
#include <sys/timeb.h>
#include <fstream>
#include <set>
#include <cmath>
#include <iomanip>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 1100000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;


bool pairCompare(const Pi& firstElof, const Pi& secondElof)
{
	return firstElof.second > secondElof.second;
}

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

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

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

	int n, m;
	cin >> n >> m;
	vi a(n);
	vPi x(m);
	rep(i, n) cin >> a[i];
	sort(all(a));
	rep(i, m) {
		int b, c;
		cin >> b >> c;
		x[i] = mp(b, c);
	}
	sort(all(x), pairCompare);
	int idx = 0;
	rep(i, m) {
		if (x[i].second > a[idx]) {
			rep(j, x[i].first) {
				if (x[i].second <= a[idx]) break;
				a[idx] = x[i].second;
				idx++;
			}
		}
	}

	ll ans = 0;
	rep(i, n) {
		ans += a[i];
	}

	cout << ans << endl;



	return 0;
}



Measured memory_bytes: 1408
# aising2020_c.py
N = int(input())
ans=[0]*(N+1)
for i in range(1,int(N**0.5)):
    for j in range(1,int(N**0.5)):
        for k in range(1,int(N**0.5)):
            num = i**2+j**2+k**2+i*j+j*k+k*i
            if num<=N:
                ans[num] += 1
for i in ans[1:]:
    print(i)


Measured memory_bytes: 9408
#include<stdio.h>
 

struct NODE {

  int right;
  int left;
  int parent;
   
};
typedef struct NODE NODE;

#define MAX 25
#define ROOT -1
#define NONODE -1
 

 
NODE nodes[ MAX+1 ];

void walkPreorder( int i );
void walkInorder( int i );
void walkPostorder( int i );


 
int main( void ) 
{   
    int n;
    int root,left,right,id;
    int i;
            
    scanf( "%d", &n );
 
    for( i=0; i<n; i++ ) {
        nodes[i].parent=ROOT;
    }    
    for( i=0; i<n; i++ ) {
        scanf( "%d%d%d", &id, &left, &right );
        nodes[id].left=left;
        if( -1 != left ) {
            nodes[left].parent=id;
        }
        nodes[id].right=right;
        if( -1 != right ) {
            nodes[right].parent=id;
        }
    }
    root=ROOT;
    for( i=0; i<n; i++ ) {
        if( ROOT == nodes[i].parent ) {
            root=i;
            break;
        }
     }
    printf( "Preorder\n" );
    walkPreorder( root );
    printf( "\n" );
     
    printf( "Inorder\n" );
    walkInorder( root );
    printf( "\n" );
     
    printf( "Postorder\n" );
    walkPostorder( root );
    printf( "\n" );
 
    return 0;
}


void walkPreorder( int i )
{
    if( NONODE == i ) { return; }
     
    printf( " %d", i );
    walkPreorder( nodes[i].left );
    walkPreorder( nodes[i].right );
     
    return;
}

void walkInorder( int i )
{
    if( NONODE == i ) { return; }
     
    walkInorder( nodes[i].left );
    printf( " %d", i );
    walkInorder( nodes[i].right );
     
    return;
}


void walkPostorder( int i )
{   
    if( NONODE == i ) { return; }
 
    walkPostorder( nodes[i].left );
    walkPostorder( nodes[i].right );
    printf( " %d", i );
     
    return;
}



Measured memory_bytes: 2092
#include<iostream>
#include<cstring>
#include<cassert>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<time.h>
#include<algorithm>
using namespace std;
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define rep(i,n) REP(i,1,n)
#define rep0(i,n) REP(i,0,n-1)
#define repG(i,x) for(ll i=pos[x];~i;i=e[i].next)
#define ll long long
#define db double
const ll N=1e6+7;
const ll INF=1e9+7;
const ll mod=998244353;
ll Pow(ll x,ll y){
	ll ans=1,now=x;
	while(y){
		if(y&1)ans=ans*now%mod;
		now=now*now%mod;
		y>>=1;
	}
	return ans;
}
ll f[N],s[N],g[N];
ll ans=0,m=1000000;
ll n;

int main(){
	scanf("%lld",&n);
	rep(i,n){
		ll x; scanf("%lld",&x);
		ans=(ans+mod-x)%mod;
		s[x]=(s[x]+x)%mod;
	}
	rep(i,m)for(ll j=i;j<=m;j+=i)g[i]=(g[i]+s[j])%mod;
	rep(i,m)g[i]=g[i]*g[i]%mod;
	for(ll i=m;i;i--){
		f[i]=g[i];
		for(ll j=i+i;j<=m;j+=i)f[i]=(f[i]-f[j]+mod)%mod;
		ans=(ans+f[i]*Pow(i,mod-2))%mod;
	}
	ll u=ans*Pow(2,mod-2)%mod;
	printf("%lld\n",u);
	return 0;
}


Measured memory_bytes: 23680
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        //var n = int.Parse(Console.ReadLine());
        decimal[] abx = Console.ReadLine().Split().Select(decimal.Parse).ToArray();
        var a = abx[0];
        var b = abx[1];
        var x = abx[2];

        //0-a-1を求める
        var tmp1 = Math.Floor((a - 1) / x) + 1;

        //0-bを求める
        var tmp2 = Math.Floor(b / x) + 1;

        // 出力
        var ans = tmp2 - tmp1;
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13396
#include<iostream>

using std::cout;
using std::cin;
using std::endl;

int main(){
    int N, M, C;
    cin >> N >> M >> C;
    int B[M] = {};
    for(int  i = 0; i < M; ++i){
        cin >> B[i];
    }
    int sum[N] = {};
    int each[M] = {};
    int counter = 0;
    for(int i = 0; i < N; ++i){
        for(int k = 0; k < M; ++k){
            cin >> each[k];
            sum[i] += each[k] * B[k];
        }
        sum[i] += C;
        if(sum[i] > 0)
            ++counter;

    }
    cout << counter << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		long K = sc.nextLong();
		long cur = 5000L * (long) 1e12;
		for (int i = 0; i < str.length(); ++i) {
			long v = str.charAt(i) - '0';
			if (v == 1) {
				--K;
				if (K == 0) {
					System.out.println(v);
					return;
				}
			} else {
				System.out.println(v);
				return;
			}
		}

	}
}


Measured memory_bytes: 21844
#include<stdio.h>
//#include<windows.h>
//#include<errno.h>
#include<stdlib.h>
#include<stddef.h>

#define Iset int i,j,l
#define man 10000
#define cn continue

int pas[101], dt[101][4][4];

int main(){
	int n, k;
	Iset;
	int ans = 0;
	scanf("%d%d", &n, &k);
	for (i = 0; i < k; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		pas[a] = b;
	}
	dt[0][0][0] = 1;
	for (i = 1; i <= n; i++) {
		if (pas[i] == 0) {
			for (j = 1; j <= 3; j++) {
				for (k = 0; k <= 3; k++) {
					for (l = 0; l <= 3; l++) {
						if (j == k && l == k) cn;
						dt[i][j][k] += dt[i - 1][k][l];
						dt[i][j][k] %= man;
		}}}}
		else {
			for (k = 0; k <= 3; k++) {
				for (l = 0; l <= 3; l++) {
					if (pas[i] == k && l == k)cn;
					dt[i][pas[i]][k] += dt[i - 1][k][l];
					dt[i][pas[i]][k] %= man;
	}}}}
	for (i = 1; i <= 3; i++) {
		for (j = 1; j <= 3; j++) {
			ans += dt[n][i][j];
			ans %= man;
	}}
	printf("%d\n", ans);
	return 0;
}


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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;

int main(){
  int X;
  cin>>X;
  bool flag[1001] = {0};
  flag[1] = 1;
  for(int i(2);i<40;i++){
    int tmp(i);
    while(tmp*i<=1000){
      flag[tmp*i] = 1;
      tmp*=i;
    }
  }
  int ans(0);
  for(int i(1);i<=X;i++){
    if(flag[i]) ans =  i;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct edge
{
    int to,col,val;
    edge(int _to=0,int _col=0,int _val=0)
    {
        to=_to;
        col=_col;
        val=_val;
    }
};
vector<edge>G[maxn];

struct Query
{
    int op,col,val,id;
    Query(int _op=0,int _col=0,int _val=0,int _id=0)
    {
        op=_op;
        col=_col;
        val=_val;
        id=_id;
    }
};
vector<Query>query[maxn];

int n,Q,ans[maxn],c[maxn],d[maxn];

void dfs(int v,int fa,int sum)
{

    for(int i=query[v].size()-1;i>=0;i--)
    {
        Query e=query[v][i];
        int tmp=sum-c[e.col]+d[e.col]*e.val;
        if(e.op==1)
            ans[e.id]+=tmp;
        else
            ans[e.id]-=2*tmp;
    }

    for(int i=G[v].size()-1;i>=0;i--)
    {

        edge e=G[v][i];
        if(e.to==fa)
            continue;
        c[e.col]+=e.val;
        d[e.col]++;
        dfs(e.to,v,sum+e.val);
        c[e.col]-=e.val;
        d[e.col]--;
    }
}


int lg[maxn],f[maxn][22],dep[maxn];

void pre_dfs(int v,int fa)
{
    dep[v]=dep[fa]+1;
    f[v][0]=fa;
    for(int i=1;(1<<i)<=dep[v];i++)
        f[v][i]=f[f[v][i-1]][i-1];
    for(int i=G[v].size()-1;i>=0;i--)
    {
        int u=G[v][i].to;
        if(u==fa)
            continue;
        pre_dfs(u,v);
    }
}

int LCA(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    while(dep[x]!=dep[y])
    {
        int h=lg[dep[x]-dep[y]];
        x=f[x][h];
    }
    if(x==y)
        return x;
    for(int i=lg[dep[x]];i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    for(int i=2;i<maxn;i++)
        lg[i]=lg[i/2]+1;

    scanf("%d%d",&n,&Q);
    for(int i=1;i<n;i++)
    {
        int A,B,C,D;scanf("%d%d%d%d",&A,&B,&C,&D);
        G[A].push_back(edge(B,C,D));
        G[B].push_back(edge(A,C,D));
    }

    pre_dfs(1,0);

    for(int i=1;i<=Q;i++)
    {
        int x,y,u,v;
        scanf("%d%d%d%d",&x,&y,&u,&v);
        int w=LCA(u,v);
        query[u].push_back(Query(1,x,y,i));
        query[v].push_back(Query(1,x,y,i));
        query[w].push_back(Query(-1,x,y,i));
    }
    dfs(1,0,0);
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]);
    return 0;
}


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

const int MAX_NODES = int(2e6) + 10;

struct Trie {
	int val;
	bool rev;
	std::vector<std::pair<int, int> > go;
	void push() {
		if (!rev || go.empty())
			return;
		rev = 0;
		int p1, p2;
		for (int i = 0; i < 3; ++i) {
			if (go[i].first == 1)
				p1 = i;
		}
		for (int i = 0; i < 3; ++i) {
			if (go[i].first == 2)
				p2 = i;
		}
		// std::cout<<p1<<" "<<p2<<std::endl;
		std::swap(go[p1].first, go[p2].first);
	}
	void debug(int id) {
		std::cout << id << ": " << std::endl;
		for (int i = 0; i < 3; ++i)
			std::cout << go[i].first << " " << go[i].second << std::endl;
	}
} trie[MAX_NODES];

int n, base, trie_tot = 1;
int pow_3[20], ans[MAX_NODES];

void build(int cur, int dep, int val) {
	if (dep == base + 1) {
		trie[cur].val = val;
		return;
	}
	for (int i = 0; i < 3; ++i) {
		trie[cur].go.emplace_back(i, ++trie_tot);
		build(trie_tot, dep + 1, val + pow_3[dep - 1] * i);
	}
	// trie[cur].debug(cur);
}

void modify(int cur) {
	// std::cout<<cur<<std::endl;
	if (trie[cur].go.empty())
		return;
	// trie[cur].debug(cur);
	if (trie[cur].rev) {
		trie[cur].push();
		for (int i = 0; i < 3; ++i) {
			// std::cout<<i<<std::endl;
			trie[trie[cur].go[i].second].rev ^= 1;
		}
	}
	for (int i = 0; i < 3; ++i) {
		(++trie[cur].go[i].first) %= 3;
		if (!trie[cur].go[i].first)
			modify(trie[cur].go[i].second);
	}
}

void dfs(int cur, int p, int dep) {
	if (trie[cur].go.empty()) {
		ans[trie[cur].val] = p;
	} else {
		if (trie[cur].rev) {
			trie[cur].push();
			for (int i = 0; i < 3; ++i)
				trie[trie[cur].go[i].second].rev ^= 1;
		}
		for (int i = 0; i < 3; ++i) 
			dfs(trie[cur].go[i].second, p + pow_3[dep - 1] * trie[cur].go[i].first, dep + 1);
	}
}

int main() {
	scanf("%d", &base);
	pow_3[0] = 1;
	for (int i = 1; i <= base; ++i) {
		pow_3[i] = pow_3[i - 1] * 3;
	}
	n = pow_3[base];
	build(1, 1, 0);
	std::string opt;
	std::cin >> opt;
	for (auto c : opt) {
		// std::cout<<c<< "\n";
		if (c == 'S')
			trie[1].rev ^= 1;
		else
			modify(1);
	}
	dfs(1, 0, 1);
	for (int i = 0; i < n; ++i) {
		printf("%d ", ans[i]);
	}
}

Measured memory_bytes: 81584
n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=0
for i in range(k+1):
  l=min(k-i,n)
  for a in range(l+1):
    b=l-a
    if b==0:
      sub=v[:a]
    else:
      sub=v[:a]+v[-b:]
    h=min(len(sub),i)
    for j in range(h):
      m=min(sub)
      if m<0:
        sub.remove(m)
    ans=max(ans,sum(sub))

print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <vector>
 
using namespace std;
const double PI=3.14159265358979323846;
 
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {

	int k, s;

	cin >> k >> s;

	int cut = 0;
	int z;
	rep(i, k + 1) {
		rep(j, k + 1) {
			z = s - i - j;
			if (0 <= z && z <= k) cut++;
		}
	}

	cout << cut << endl;
}

Measured memory_bytes: 256
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val s = sc.next
  val t = sc.next

  val duplicate = n - (0 to n).find { i => t.startsWith(s.substring(i))}.get
  val res = n + n - duplicate

  println(res)
}

Measured memory_bytes: 27288
from collections import defaultdict
import math
MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    AB = [ZZ() for _ in range(N)]
    AB = [[a, b] for a, b in AB if a != 0 or b != 0] # 零ベクトルは除外
    cnt_0 = N - len(AB) # 零ベクトルの個数
    vec = defaultdict(int) # ベクトル個数の管理

    #既約化
    for i in range(len(AB)):
        a, b = AB[i]
        if a < 0: a, b = -a, -b
        if a == 0: b = abs(b)
        g = math.gcd(a, b)
        a //= g
        b //= g
        vec[(a, b)] += 1

    output = 1
    used = set()
    for v in vec.keys():
        if v in used: continue
        a, b = v
        inv = (-b, a) if b < 0 else (b, -a)
        if b == 0: inv = (b, abs(a))
        if inv in vec.keys():
            output *= (pow(2, vec[v], MOD) + pow(2, vec[inv], MOD) - 1)
        else: output *= pow(2, vec[v], MOD)
        output %= MOD
        used.add(v)
        used.add(inv)

    output += cnt_0 - 1
    output %= MOD
    print(output)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 121192
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; i64 k; scanf("%d%lld", &n, &k); std::vector<std::vector<int>> g(n);
	for(int i = 0; i < n - 1; i++) {
		int a, b; scanf("%d%d", &a, &b);
		
		g[a - 1].push_back(b - 1);
		g[b - 1].push_back(a - 1);
	}
	
	const int MOD = 1e9 + 7;
	std::vector<i64> fact(n + 1, 1);
	for(int i = 0; i < n; i++) fact[i + 1] = fact[i] * (k - i - 2) % MOD;
	
	i64 ans = k;
	std::function<void (int, int, bool)> solve = [&](int v, int par, bool f) {
		int deg = 0;
		for(auto e: g[v]) {
			if(e == par) continue;
			solve(e, v, false); deg++;
		}
		
		if(f) (ans *= fact[deg - 1] * (k - 1) % MOD) %= MOD;
		else (ans *= fact[deg]) %= MOD;
	};
	if(n == 1) ans = k;
	else solve(0, -1, true);
	
	printf("%lld\n", ans);
	return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);i++)

// 自動でmodを取ってくれる整数型
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
// const int mod = 1000000007;
const int mod = 998244353;
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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const { // ans=mint(a).pow(b); // a^b
    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 { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

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

// a^n mod を計算する
long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//////////////////////////
int main(){
    int N,K;
    cin>>N>>K;
    vector<int> L(K),R(K);
    rep(i,K){ 
        cin>>L[i]>>R[i];
    }
    vector<mint> dp(N+1),cs(N+1);
    dp[1]=1;
    cs[1]=1;
    for(int i=2;i<=N;i++){
        rep(j,K){
            dp[i]+=cs[max(i-L[j],0)]-cs[max(i-R[j]-1,0)];
        }
        cs[i]=cs[i-1]+dp[i];
    }
    cout<<dp[N]<<endl;
}


Measured memory_bytes: 6408
/*author:anshumanc007
   created on:09/01/2019
            */
//EMBRACE THE STRUGGLE!!!
#include <bits/stdc++.h>
#include <queue>
#include <stack>
using namespace std;
#define MAX 100005
long long int MOD=1e9+7;
long long int INF=1e18;

long long int dp[3005][3005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long int i,j,k,l,m,n,o,p,q,r,x,y,a,b,mini=INF,maxi=0,cnt=0,W,ans,iter=0,len;
    cin>>n;
    long long int A[n+1];
    for(i=1;i<=n;i++)
    {
        cin>>A[i];
    }
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            dp[i][j]=0;
        }
    }
    for(i=0;i<=n;i++)
    {
        dp[i][i]=A[i];
    }
    for(len=2;len<=n;len++)
    {
        for(i=1;i<=n-len+1;i++)
        {
            j=i+len-1;
            if(len%2==0)
            dp[i][j]=min(dp[i+1][j]-A[i],dp[i][j-1]-(A[j]));
            else
                dp[i][j]=max(dp[i+1][j]+A[i],dp[i][j-1]+A[j]);
            
        }
    }
    if(n%2==0)
    cout<<-1*dp[1][n]<<endl;
    else
    {
        cout<<dp[1][n]<<endl;
    }
   

    
}

Measured memory_bytes: 70784
#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include <cmath>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
#define downint greater<int>()
#define downchar greater<char>()
#define downstring greater<string>()
void tmpInit(int *c,ll m) {ll i;rep(i,m) c[i]=i;}
ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1){
      res *= a; if(mod>=1) res %= mod;
    }
    a *= a; if(mod>=1) a %= mod;
    n >>= 1;
  }
  return res;
}
void initialize(){
  
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0,sum=0;
  int a[LIMIT2]={0};
  ll b[LIMIT2]={0};
  char s[LIMIT1];
  ll dp[LIMIT2]={0};
  
  cin >> n >> k;
  rep(i,n) cin >> a[i];
  
  rep(j,k){
    sum=0;
    rep(i,n){
      dp[max(0,i-a[i])]++;
      dp[min(n,i+1+a[i])]--;
    }
    rep(i,n){
      sum += dp[i];
      b[i] = sum;
      //cout << sum << " ";
    }
    rep(i,n){
      dp[max(0,i-a[i])]--;
      dp[min(n,i+1+a[i])]++;
      a[i] = b[i];
    }
    sum=0;
    rep(i,n) sum+=a[i];
    if(sum>=n*n) break;
  }
  rep(i,n){
    cout << a[i] << (i==n-1 ? '\n' : ' ');
  }
  return 0;
}

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

int main()
{
    int t,x,y;
    while(~scanf("%d",&t))
    {
        if(t==1)
            printf("Hello World\n");
        if(t==2)
        {
            scanf("%d %d",&x,&y);
            printf("%d\n",x+y);
        }
    }
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] A = new int[N];
		for(int i=0; i<N; i++ ) {
			A[i] = scan.nextInt();
		}
		scan.close();
		int r = bubbleSort(A, N);
		for(int i=0; i<=N-1; i++) {
			if(0<i) {
				System.out.print(" ");
			}
			System.out.print(A[i]);
		}
		System.out.println();
		System.out.println(r);

	}

	public static int bubbleSort(int[] A, int N) {
		int replaceCount = 0;
		boolean flag = true; // 逆の隣接要素が存在する
		while(flag) {
			flag = false;
			for(int j=N-1; j>=1; j--) {
				if(A[j] < A[j-1]) {
					int t = A[j];
					A[j] = A[j-1];
					A[j-1] = t;
					flag = true;
					replaceCount++;
				}
			}
		}
		return replaceCount;
	}

}



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

int main(){
  int n;
  cin >> n;
  vector<int>tako(n);
  for(int i=0;i<n;i++)
    cin >> tako.at(i);
  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i!=j)
        ans+=tako.at(i)*tako.at(j);
    }
  }
  cout << ans/2 << endl;
  return 0;
}

Measured memory_bytes: 3572
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  #pre = MS(i,int(s),pre)
  pre += int(s)*i
  pre %= p
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)



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

int main() {
    int K, N;
    cin >> K >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    int ans = A[0] + K - A[N - 1];
    for (int i = 0; i < N - 1; ++i) {
        int d = A[i + 1] - A[i];
        ans = max(ans, d);
    }
    cout << K - ans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int ans = 700;
    string S;
    cin >> S;
    for (int i = 0; i < 3; i++)
        if (S[i] == 'o')
            ans += 100;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256