akhauriyash/Code-Regression huggingface dataset:
import heapq

s = []
h, w = map(int, input().split())
for _ in range(h):
    s.append(list(input().strip()))

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue

        q = [(0, (i, j))]
        mins = [[h * w for _ in range(w)] for _ in range(h)]
        visited = [[0 for _ in range(w)] for _ in range(h)]
        while len(q) > 0:
            c, (x, y) = heapq.heappop(q)
            ans = max(ans, c)
            if visited[x][y]:
                continue
            visited[x][y] = True
            for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if nx < 0 or nx >= h or ny < 0 or ny >= w or s[nx][ny] == '#':
                    continue
                if visited[nx][ny]:
                    continue
                if mins[nx][ny] > c + 1:
                    mins[nx][ny] = c + 1
                    heapq.heappush(q, (c + 1, (nx, ny)))

print(ans)


Measured memory_bytes: 79272
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cctype>
#include<cmath>
#include<cstring>
#include<sstream>
#include<set>
#include<map>
#define maxn 100000007
using namespace std;
typedef long long ll;
int main()
{
    int n;
    cin>>n;
    int s=0;
    if(n<10)
        s=n;
    else if(n<100)
        s=9;
    else if(n<1000)
        s=n-90;
    else if(n<10000)
        s=909;
    else if(n<100000)
        s=909+n-10000+1;
    else
        s=90909;
    cout<<s;
    return 0;
}


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

int main() {
    string s;
    cin >> s;
    string ans = "";

    for(int i = 0; i < s.size(); i++) {
        if(s.at(i) == '0') ans.push_back('0');
        else if(s.at(i) == '1') ans.push_back('1');
        else {
            if(ans.size() != 0) {
                ans.pop_back();
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3560
package main
import (
  "fmt"
)
func main() {
  var a, b, c, k int64
  fmt.Scan(&a, &b, &c, &k)
  var result int64
  if k%2 == 0 {
    result = a - b
  } else {
    result = b - a
  }
  fmt.Println(result)
}

Measured memory_bytes: 512
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<queue>

using std::cout;
using std::cin;
using std::setw;
using std::setfill;
using std::string;
using std::pair;
using std::vector;
using std::queue;
using std::deque;
using std::priority_queue;
using std::sort;
using std::greater;
using std::max;
using std::min;

using lli = long long int;
using ulli = unsigned long long int;

//#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

int N, l, r;
lli ans = 0;

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

	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> l >> r;
		ans += r-l+1;
	}
	cout << ans;
  return 0;
}


Measured memory_bytes: 256
const BKRT = "\n";
const SPAC = " ";
const NOSP = "";

function Main(input){
	input = [].concat(...input.split(BKRT).map(a=>a.split(SPAC)));
  const strShift = ()=>input.shift();
  const intShift = ()=>~~input.shift();
  
  var A = intShift();
  var B = intShift();
  var C = intShift();
  
  A -= C;
  B += C;
  
  return ~~Math.floor(A/B);
}

// If you are interested in the algorithms I used, 
// there is no need to read down from this line.

((b,c,d)=>"undefined"!=typeof require?console.log(Main(require("fs").readFileSync("/dev/stdin","utf8"))):[b=b.split("\n").slice(1,-1).join("\n"),c=function(){try{return Main(b)}catch(f){return f.stack||f.message}}(),d=typeof c,"string"==d||(c=JSON.stringify(c)),$("<form>").append([[10,b],0,[1,d],0,[10,c]].map(f=>$(f?"<textarea>":"<br>",f&&{rows:f[0],cols:40,text:f[1]}))).appendTo("body")])(`
12 3 1
`);

Measured memory_bytes: 7372
def main():
    N = int(input())
    a = [0] + [int(ele) for ele in input().split()]
    a.sort()
    ans = 0
    for i in range(1,N+1):
        diff = a[i] - a[i-1]
        ans += diff

    tmp = ans
    ans =0
    a.sort(reverse=True)
    for i in range(1,N):
        diff = abs(a[i] - a[i-1])
        ans += diff
    ans = min(ans,tmp)
    print(ans)

       




if __name__=="__main__":
    main()

Measured memory_bytes: 3064
#include <stdio.h>
#include <ctype.h>

int main(){
  char a[20],b[20],c[20];
  int i;
  scanf("%s %s %s",a,b,c);
  printf("%c%c%c\n",toupper(a[0]),toupper(b[0]),toupper(c[0]));

  return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

string s;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    cin>>s;
    string ans(s.size(),'x');
    print(ans);
    return 0;
}

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

class UniTree { 
    public:
    
    // par[i]       : ノードiの親
    // hight[i]     : ノードiの高さ
    vector<int> par, hight;
 
    //  [引数]   
    //          int size            : UnionFind木の大きさ
    //
    //  [機能]   
    //          UnionFind木の初期化（親と高さの初期化）
    UniTree() {}
    UniTree(int size){
        par = vector<int>(size + 1, 0);
        hight = vector<int>(size + 1, 0);
        for(int i=0 ;i<=size ;i++ ){
            par[i] = i;
        }
    }
 
    //  [引数]   
    //          int x   : 親を求めたいノードの番号
    //
    //  [機能]   
    //          ノードxの親を求めながら、再帰的に経路圧縮を行う
    int FindSet(int x){
        if(par[x] != x){
            par[x] = FindSet(par[x]);
        } 
        
        return (par[x]);
    }
 
    //  [引数]   
    //          int x   : ノードx
    //          int y   : ノードy
    //
    //  [機能]   
    //          ノードxとノードyが同じグループならtrue、
    //          そうでなければfalseを返す
    bool Same(int x, int y){
        int X, Y;
 
        X = FindSet(x);
        Y = FindSet(y);
 
        if(X == Y){
            return (true);
        } else {
            return (false);
        }
    }
 
    //  [引数]   
    //          int x   : ノードx
    //          int y   : ノードy
    //
    //  [機能]   
    //          ノードxとノードyが同じグループに属するようにする
    void Link(int x, int y){
        int X, Y;
 
        X = FindSet(x);
        Y = FindSet(y);
 
        if(hight[X] > hight[Y]){
            par[Y] = X;
        } 
        else if(hight[Y] > hight[X]){
            par[X] = Y;    
        } else {
            par[X] = Y;
            hight[Y] = X;
        }
        return ;
    }
};

signed main() {
    int n, q, a, b, ans[200001] = {};
    int find[200001], ans1 = 0;
    cin >> n >> q;
    UniTree tree = UniTree (n);
    
    for (int i = 0; i < q; i++ ) {
        cin >> a >> b;
        tree.Link(a, b);
    }
    
    for (int i = 0; i < n; i++ ) {
        find[i] = tree.FindSet(i+1);
    }
    
    for (int i = 0; i < n; i++ ) {
        ans[ find[i] ]++;
        if (ans1 < ans[ find[i] ]) {
            ans1 = ans[ find[i] ];
        } 
    }
    
    cout << ans1 << endl;
    
    return (0);
}

Measured memory_bytes: 6340
var area = (input) => {
  var lengthList = input.split(' ');
  var varticalLength = Number.parseInt(lengthList[0]);
  var horizontalLength = Number.parseInt(lengthList[1]);
  
  console.log(`${varticalLength * horizontalLength / 2}`);
}

process.stdin.resume();
process.stdin.setEncoding('utf8');
var inputString = '';

process.stdin.on('data', function(chunk) {
  inputString += chunk;
});

process.stdin.on('end', function() {
  area(inputString);
});

Measured memory_bytes: 7500
#include <bits/stdc++.h>
using namespace std;
//彩色判定だねうふふ
#define int long long 
int N, M;
vector < int > G[100005];
int cmp[100005];
bool dfs(int v, int color)
{
    bool ret = false;
    if(~cmp[v]) {
        if(cmp[v] == color) return (false);
        else return (true);
    }
    cmp[v] = color;
    for(int i = 0; i < G[v].size(); i++) ret |= dfs(G[v][i], 1 - color);
    return (ret);
}
signed main()
{
    memset(cmp, -1, sizeof(cmp));
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B; --A, --B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    if(dfs(0, 0)) {
        cout << ((N - 1) * N / 2) - M << endl;
    } else {
        int asum = 0, bsum = 0;
        for(int i = 0; i < N; i++) {
            asum += cmp[i] == 0;
            bsum += cmp[i] == 1;
        }
        cout << asum * bsum - M << endl;
    }
    return (0);
}


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

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REV(i,j,k) for(int i=j;i>=k;i--)
#define FORR(i,j,k,l) for(int i=j;i<=k;i+=l)
#define inf         freopen("in.txt", "r", stdin)
#define outf        freopen("out.txt", "w", stdout)
#define pf          printf
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c)    scanf("%d %d %d", &a, &b, &c)
#define clean(mat,n)   FOR(i,0,n) mat[i].clear()
#define minn          (long long)-1000000000000000000
#define maxx          (long long) 1000000000000000000
#define M          1000000007
#define M_PI           3.14159265358979323846  /* pi */
#define LL           long long
#define NL '\n'
#define cnd tree[idx]
#define lnd (idx<<1)
#define rnd ((idx<<1)+1)
#define PB push_back
#define F first
#define S second
#define MAX 100010
#define MP make_pair
#define valid(nx,ny)  ((nx >= 0) && (nx < row) && (ny >= 0) && (ny < col))
#define LD long double
typedef pair<int,int> PR;

LL dp[MAX], bm[MAX], ara[MAX], n, k;

int main()
{
    ios::sync_with_stdio(false);
    //inf;
    //outf;

    cin >> n >> k;
    FOR(i,0,n-1) cin >> ara[i];

    dp[0] = 1;
    FOR(i,0,n-1)
    {
        FOR(j,0,k)
        {
            int l = j, r = j + ara[i] + 1; r = min(r, MAX-1);
            bm[l] += dp[j]; if(bm[l] >= M) bm[l] -= M;

            if(bm[r] < dp[j]) bm[r] += M;
            bm[r] -= dp[j]; if(bm[r] >= M) bm[r] -= M;
        }
        FOR(j,1,k)
        {
            bm[j] += bm[j - 1];
            if(bm[j] >= M) bm[j] -= M;
        }
        FOR(j,0,k)
        {
            dp[j] = bm[j];
            bm[j] = 0;
           /// cout << dp[j] << ' ';
        }
        ///cout << endl << endl;
    }

    cout << dp[k] << endl;

    return 0;
}




Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi acos(-1.0)

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    REP(i, s.size()){
        if(i % 2 == 0) cout << s[i];
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 592
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <math.h>
#include <algorithm>
#include <deque>
#include <queue>
#include <climits>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ve vector
#define umap unordered_map
#define iter iterator

void solve() {
    int n,m;
    cin>>n>>m;
    int p = 1 << m;
    int t = m*1900 + (n-m)*100;
    cout << t*p << endl;
}

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

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author NikuKyabe
 */

#include <iostream>
#include <fstream>

#include "bits/stdc++.h"

using namespace std;
#define int long long
#define ITR(itr, mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
typedef vector<int> vec;


class C {
public:
    vec ans;
    int n;
    string s;

    void dfs(int v, int sum, int t) {
      if (v == n) {
        ans.push_back(sum + t);
        return;
      }
      dfs(v + 1, sum, t * 10 + (s[v] - '0'));
      dfs(v + 1, sum + t, s[v] - '0');
    }

    void solve(std::istream &in, std::ostream &out) {
      in >> s;
      n = s.length();
      dfs(1, 0, s[0] - '0');
      int ret = 0;
      ITR(itr, ans) {
        ret += *itr;
      }
      out << ret << endl;
    }
};


signed main() {
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout << fixed;
  C solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}


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

#define MAX 100005

int search(int S[], int n, int key) {
  int high, mid, low;
  high = n, low = 0;
  mid = (high + low) / 2;

    while ( S[mid] != key && high > low) {
      if (S[mid] > key) high = mid;
      else if (S[mid] < key) low = mid + 1;
      mid = (high + low) / 2;
    }

  return S[mid] == key;
}

int main() {
  int n, q;
  int S[MAX];
  int key;
  int cnt = 0;

  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    cin >> S[i];
  }

  cin >> q;
  for ( int i = 0; i < q; i++ ) {
    cin >> key;
    if ( search(S, n, key) ) cnt++;
  }

  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 3472
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
	string[] input = Console.ReadLine().Split(' ');//Splitで区切り文字を指定して複数個受け取る。
	long n = long.Parse(input[0]);
	long k = long.Parse(input[1]);
  long answer = 0;

  long a = n / k;
  a *= a*a;
  answer += a;

    if(k % 2 == 0)
    {
      a = n / k;
      if(n/k*k+(k/2)<=n)
      {
        a ++;
        a *= a*a;
        answer += a;
      }else
      {
      a *= a*a;
      answer += a;
      }
    }  
	
	Console.WriteLine(answer);//WriteLineをWriteとすると、改行なしで出力。
	}
}

Measured memory_bytes: 11092
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
typedef long long ll;
using namespace std;

int main(void){
  int n,v[20],c[20];
  cin>>n;
  int i;
  int ans=0;
  for(i=0;i<n;i++){
   cin>>v[i]; 
  }
  for(i=0;i<n;i++){
   cin>>c[i]; 
  }
  for(i=0;i<n;i++){
   if(v[i]>c[i]){
     ans+=(v[i]-c[i]);
   }
  }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAX_N 200001
#define mod 1000000007
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define REV(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin(), v.end()
#define pb push_back
const ll INF = 9e18;
ll n;
string s[MAX_N];
map<string, ll> m;

signed main(){
    cin >> n;
    REP(i, n) cin >> s[i];
    REP(i, n){
        m[s[i]]++;
    }
    ll max_cnt = 0;
    vector<string> vs;
    for(const auto& kv: m){
        // cout << kv.first << " " << kv.second << endl;
        max_cnt = max(max_cnt, kv.second);
    }
    for(const auto& kv: m){
        if(kv.second == max_cnt) vs.pb(kv.first);
    }
    sort(vs.begin(), vs.end());
    for(auto& str: vs) cout << str << endl;
    return 0;
}

Measured memory_bytes: 29428
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2298
// ?????????????????§?????????????£????????????????????????????
// ???????????????1????£?????????¨T?§??????????????????¢?????????????????§???????????????
// ??????????????? 1/T ???/?§? ??????????????§?£?????????????????????????????????¢??????????????¨????????????

#include <iostream>
#include <cstdio>
using namespace std;

const double eps = 1e-10;

int main() {
  int N;
  double K;
  double T, U, V, L;
  cin >> N >> K >> T >> U >> V >> L;
  K = K+1;
  double D[210];
  for (auto i=0; i<N; i++) {
    cin >> D[i];
  }
  double nowlength = 0;
  int nown = 0;
  double nowcar = 0;
  double ans = 0;
  double next = 0;
  double nowvel = 0;
  while (nowlength + eps < L) {
    if (nown < N) {
      next = D[nown] - nowlength;
    } else {
      next = L - nowlength;
    }
    if (nowcar < eps) {
      // cerr << "does not eat" << endl;
      nowvel = U;
      ans += next/nowvel;
      nowlength += next;
      if (nown < N) {
        nowcar = min(nowcar+1, K);
      }
      nown++;
    } else {
      // cerr << "eat" << endl;
      nowvel = V;
      double ablelength = V * T * nowcar;
      if (ablelength < next - eps) {
        // cerr << "does not reach" << endl;
        nowlength += ablelength;
        ans += ablelength/nowvel;
        nowcar = 0;
      } else {
        // cerr << "reach" << endl;
        nowlength += next;
        ans += next/nowvel;
        nowcar -= next/(V * T);
        if (nown < N) {
          nowcar = min(nowcar+1, K);
        }
        nown++;
      }
    }
    /*
    cerr << "nowlength = " << nowlength
         << ", nown = " << nown
         << ", nowcar = " << nowcar
         << ", ans = " << ans 
         << ", nowvel = " << nowvel
         << ", next = " << next
         << endl;
    */
  }
  printf("%0.7lf\n", ans);
}

Measured memory_bytes: 1240
#include <stdio.h>
      
int main(void) {
	int i;
	long ans, n, k, l;

    scanf("%ld%ld", &n, &k);
    
    l = 1;
    for (i = 0; i < n - 1; i++) {
    	l *= ( k - 1 );
    }
    	
    ans = k * l;
    
    printf("%ld\n", ans);
    
    return 0;
}

Measured memory_bytes: 128
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

if __name__ == "__main__":
    while True:
        try:
            n = int(input())
            print(len(primes(n)))
        except:
            break



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

int main(){
    string s;
    cin >> s;
    int idx = s.size() - 1;
    while(idx >= 0){
		if(idx - 6 >= 0 && s[idx - 6] == 'd' && s[idx - 5] == 'r' && s[idx - 4] == 'e' && s[idx - 3] == 'a' && s[idx - 2] == 'm' && s[idx - 1] == 'e' && s[idx] == 'r'){
			idx = idx - 7;
		}
		else if(idx - 4 >= 0 && s[idx - 4] == 'd' && s[idx - 3] == 'r' && s[idx - 2] == 'e' && s[idx - 1] == 'a' && s[idx] == 'm'){
			idx = idx - 5;
		}
		else if(idx - 5 >= 0 && s[idx - 5] == 'e' && s[idx - 4] == 'r' && s[idx - 3] == 'a' && s[idx - 2] == 's' && s[idx - 1] == 'e' && s[idx] == 'r'){
			idx = idx - 6;
		}
		else if(idx - 4 >= 0 && s[idx - 4] == 'e' && s[idx - 3] == 'r' && s[idx - 2] == 'a' && s[idx - 1] == 's' && s[idx] == 'e'){
			idx = idx - 5;
		}
		else{
			break;
		}
    }
    if(idx == -1){
		cout << "YES" << endl;
    }
    else{
		cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Data{
    int NUM;
    string str;
    int P;
};

int main(){
    int N,i;

    cin >> N;
    vector<Data> data(N);
    for(i = 0; i < N; i++){
        data[i].NUM = i + 1;
        cin >> data[i].str >> data[i].P;
    }

    sort(data.begin(), data.end(), [](const Data &a, const Data &b){
        return a.str == b.str ? a.P > b.P : a.str < b.str;
    });

    for(i = 0; i < N; i++){
        cout << data[i].NUM << endl; 
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.List;
import java.util.Scanner;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int q = scanner.nextInt();
        final String s = scanner.next();

        final List<Query> queries = IntStream.range(0, q)
            .mapToObj(i -> new Query(scanner.next().charAt(0), scanner.next().charAt(0) == 'L' ? -1 : 1))
            .collect(Collectors.toList());

        final Function<Integer, SimulationResult> simulate = current -> {
            for (final Query query : queries) {
                if (s.charAt(current) != query.symbol) {
                    continue;
                }

                if (current == 0 && query.direction == -1) {
                    return SimulationResult.LEFT_FALL;
                } else if (current == s.length() - 1 && query.direction == 1) {
                    return SimulationResult.RIGHT_FALL;
                }

                current += query.direction;
            }

            return SimulationResult.REMAIN;
        };

        if (simulate.apply(n - 1) == SimulationResult.LEFT_FALL || simulate.apply(0) == SimulationResult.RIGHT_FALL) {
            System.out.println(0);
            return;
        }

        final int mostLeft = simulate.apply(0) == SimulationResult.LEFT_FALL ? binarySearchLeft(0, n - 1, simulate) : 0;
        final int mostRight = simulate.apply(n - 1) == SimulationResult.RIGHT_FALL ? binarySearchRight(0, n - 1, simulate) : n;
        if (mostLeft >= mostRight) {
            System.out.println(0);
        } else {
            System.out.println(mostRight - mostLeft);
        }
    }

    private static int binarySearchLeft(final int begin, final int end, final Function<Integer, SimulationResult> simulate) {
        if (end - begin <= 1) {
            return end;
        }
        final int mid = (begin + end) / 2;
        final SimulationResult result = simulate.apply(mid);
        if (result == SimulationResult.LEFT_FALL) {
            return binarySearchLeft(mid, end, simulate);
        } else {
            return binarySearchLeft(begin, mid, simulate);
        }
    }

    private static int binarySearchRight(final int begin, final int end, final Function<Integer, SimulationResult> simulate) {
        if (end - begin <= 1) {
            return end;
        }
        final int mid = (begin + end) / 2;
        final SimulationResult result = simulate.apply(mid);
        if (result == SimulationResult.RIGHT_FALL) {
            return binarySearchRight(begin, mid, simulate);
        } else {
            return binarySearchRight(mid, end, simulate);
        }
    }

    private enum SimulationResult {
        LEFT_FALL, RIGHT_FALL, REMAIN
    }

    private static class Query {
        final char symbol;
        final int direction;

        Query(final char symbol, final int direction) {
            this.symbol = symbol;
            this.direction = direction;
        }
    }
}


Measured memory_bytes: 70720
#include<bits/stdc++.h>
#define rep(i, x) for(ll i = 0; i < x; i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
const ld pi = 3.141592653589793238;

signed main() {
	//ll n, k; cin >> n >> k;
	ll n = 1407, k = 38;
	vector<vector<ll>> v(k, vector<ll>(k));
	cout << n << ' ' << k << endl;
	for (int h = 1; h <= k; h++) {
		if (h == 1) { cout << h; }
		else { cout << ' ' << h; }
	}
	cout << endl;
	for (int h = 1; h <= k; h++) {
		ll z = k + 1;//h == 1
		for (int i = 0; i < k - 1; i++) {
			cout << h;
			if (h == 1) {
				for (int j = 0; j < k - 1; j++) {
					v[i][j] = z;
					cout << ' ' << z; z++;
				}
			}
			else {
				for (int j = 0; j < k - 1; j++) {
					ll ans = ((h - 2) * j) + i;
					ans %= (k - 1);
					cout << ' ' << v[j][ans];
				}
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3432
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
        return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Program
{
    static int n;
    static int[] a;
    static long[,] dp;

    public static void Main()
    {
        n = int.Parse(ReadLine());
        a = ReadIntArray();

        // dp[i, j] : i, j は deque の Pointers
        dp = new long[n,n];

        WriteLine(rec(0, n-1, 0));
    }

    static long rec(int i, int j, int turn)
    {
        if (dp[i, j] != 0) return dp[i, j];
        if (i == j) return dp[i, j] = (turn == 0) ? a[i] : - a[i];

        if (turn == 0)
            dp[i, j] = Math.Max(rec(i+1, j, 1) + a[i], rec(i, j-1, 1) + a[j]);
        else
            dp[i, j] = Math.Min(rec(i+1, j, 0) - a[i], rec(i, j-1, 0) - a[j]);

        return dp[i, j];
    }
}

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

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

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int ans=1e5;
    chmin(ans,abs((a+b)-(c+d)));
    chmin(ans,abs((a+c)-(b+d)));
    chmin(ans,abs((a+d)-(c+b)));
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3104
/*g++ main.cpp -o main.out*/
/*./main.out*/

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

const int maxn=1299710;
bool u[maxn];
int ans[maxn];
void prepare()
{
    int i,j,k;
    for(i=2; i<maxn; i++)
        u[i]=1;
    for(i=2; i<maxn; i++)
        if(u[i])
            for(j=2; j*i<maxn; j++)
                u[i*j]=0;
    for(i=2; i<maxn; i++)
        if(!u[i])
        {
            j=i;
            while(j<maxn&&!u[j])
                j++;
            j--;
            for(k=i; k<=j; k++)
                ans[k]=j-i+2;
            i=j;
        }
        else
            ans[i]=0;
}
int main ()
{
    int i,j,k;
    prepare();
    while(scanf("%d",&k)!=EOF&&k)
    {
        printf("%d\n",ans[k]);
    }
    return 0;
}


Measured memory_bytes: 9468
import java.util.Scanner;

public class Main{
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		double a,b,C;
		double S,L,h;
		a = sc.nextDouble();
		b = sc.nextDouble();
		C = sc.nextDouble();
		S = Math.sin(Math.toRadians(C)) * ((a * b) / 2);
		L = a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(Math.toRadians(C)));
		h = Math.sin(Math.toRadians(C)) * b;
		System.out.println(S);
		System.out.println(L);
		System.out.println(h);
	}
}

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

#define rep(i,n) for (int i = 0; i< (n); ++i)
#define vvec(m,n) vector<vector<int>> (int(m), vector<int>(n))
#define ALL(a) (a).begin(), (a).end()

using ll = long long;

int main(){
    int a, b, h;
    cin >> a >> b >> h;
    int area = (a + b) * h / 2;
    cout << area << endl;
}

Measured memory_bytes: 256
n = int(raw_input())
l = map(int, raw_input().split())
ans = 0
i = 0
while i < n:
    if i+1 == l[i]:
        ans += 1
        if i+1 < n and i+2 == l[i+1]:
            i += 1
    i += 1
print ans


Measured memory_bytes: 11304
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
    string s;
    getline(cin,s);
    char c;
    int C;
    for (int i = 0; i<s.size(); i++){
        if(('a' <= s[i])and(  s[i] <= 'z')){
            C=int(s[i])-32;
            s[i]=char(C);
        }else if (('A' <= s[i])and(  s[i] <= 'Z'))
        {
            C=int(s[i])+32;
            s[i]=char(C);
        }
        
        cout << s[i];
    }
    // cout << s.size<<"/n";
    cout << "\n";
    return 0;
}


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

using namespace std;

int main() {
    char s[5];
    cin >> s;
    
    string ans;
    for (int i=0;i<5-1;i++) {
        if (s[i] == s[i+1]) {
            ans="Bad";
            break;
        } else {
            ans="Good";
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;
using ll = long long;

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

  int n;
  cin >> n;
  vector<ll> l(n);
  for (int i = 0; i < n; i++)
    cin >> l[i];

  ll ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      for (int k = j + 1; k < n; k++) {
        if (l[i] == l[j] || l[j] == l[k] || l[k] == l[i])
          continue;
        if (l[i] + l[j] > l[k] && l[j] + l[k] > l[i] && l[k] + l[i] > l[j])
          ans++;
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define PB push_back
typedef long long int ll;
const int N=40;
int main(){
    int n,k,mid,tot,m,L,R,atot,from,to,cnt;
    ll l,r,ans=0,a[N],temp;
    vector<ll> dp[N];
    scanf("%d%d%lld%lld",&n,&k,&l,&r);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    mid=n/2;
    tot=1<<mid;
    for(int i=0;i<tot;i++){
        temp=0;
        cnt=0;
        for(int j=0;j<mid;j++)if(i&(1<<j)){
            temp+=a[j];
            cnt++;
        }
        dp[cnt].PB(temp);
    }
    for(int i=0;i<mid;i++)sort(dp[i].begin(),dp[i].end());
    mid=n-mid;
    atot=1<<mid;
    for(int i=0;i<atot;i++){
        temp=0;
        cnt=0;
        for(int j=0;j<mid;j++)if(i&(1<<j)){
            temp+=a[n-mid+j];
            cnt++;
        }
        if(cnt<=k&&!dp[k-cnt].empty()&&dp[k-cnt].back()+temp>=l&&dp[k-cnt].front()+temp<=r){
            L=0;
            R=(int)dp[k-cnt].size()-1;
            while(R-L>1){
                m=(R+L)>>1;
                if(temp+dp[k-cnt][m]<=r)L=m;
                else R=m;
            }
            if(temp+dp[k-cnt][R]<=r)to=R;
            else to=L;
            L=0;
            R=(int)dp[k-cnt].size()-1;
            while(R-L>1){
                m=(R+L)>>1;
                if(temp+dp[k-cnt][m]>=l)R=m;
                else L=m;
            }
            if(temp+dp[k-cnt][L]>=l)from=L;
            else from=R;
            if(to-from>=0)ans+=to-from+1;
        }
    }
    printf("%lld\n",ans);
}



Measured memory_bytes: 11796
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x;
  int sum = 0;
  cin >> x;
  
  sum += x / 100;
  x = x - 100 * (x / 100);

  sum += x / 10;
  x = x - 10 * (x / 10);
  sum += x;
  
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstring>
#include <cstdio>
#define my_abs(x) ((x) < 0 ? -(x) : (x))
int lst[100005], to[200005], pre[200005], seq[100005], tot;
int fa[100005], sum[100005], col[100005], coef[100005];
inline void add_edge(int u, int v)
{
	to[tot] = v;
	pre[tot] = lst[u];
	lst[u] = tot++;
}
void dfs(int u, int cur, int f = -1)
{
	fa[u] = f;
	sum[u] = cur;
	col[u] = cur;
	for (int i = lst[u]; ~i; i = pre[i])
	{
		if (to[i] == f)
			continue;
		dfs(to[i], -cur, u);
		sum[u] += sum[to[i]];
	}
}
int getfa(int u)
{
	if (u == fa[u])
		return u;
	return fa[u] = getfa(fa[u]);
}
int main()
try
{
	// freopen("AGC004-F.in", "r", stdin);
	memset(lst, -1, sizeof(lst));
	int n, m, x, y;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		fa[i] = i;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		if (getfa(--u) == getfa(--v))
		{
			x = u;
			y = v;
			continue;
		}
		fa[getfa(u)] = getfa(v);
		add_edge(u, v);
		add_edge(v, u);
	}
	dfs(0, 1);
	long long ans = 0;
	if (m == n - 1)
	{
		if (sum[0])
			throw false;
	}
	else if (col[x] == col[y])
	{
		if (sum[0] & 1)
			throw false;
		int val = sum[0] >> 1;
		ans += my_abs(val);
		for (int i = x; ~i; i = fa[i])
			sum[i] -= val;
		for (int i = y; ~i; i = fa[i])
			sum[i] -= val;
	}
	else
	{
		if (sum[0])
			throw false;
		for (int i = x; ~i; i = fa[i])
			coef[i]++;
		for (int i = y; ~i; i = fa[i])
			coef[i]--;
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			if (coef[i])
				seq[cnt++] = -coef[i] * sum[i];
		}
		std::sort(seq, seq + cnt);
		int val = seq[cnt >> 1];
		ans += my_abs(val);
		for (int i = 0; i < n; i++)
			sum[i] += coef[i] * val;
	}
	for (int i = 0; i < n; i++)
		ans += my_abs(sum[i]);
	printf("%lld\n", ans);
	return 0;
}
catch (bool)
{
	puts("-1");
	return 0;
}


Measured memory_bytes: 8576
#include<stdio.h>
int f[2],s[2],t[2];
int main(void)
{
    int ten[2][10],i,j,k;
    for(i = 0;i < 2;i++){
        for(j = 0;j < 10;j++){
            scanf("%d",&ten[i][j]);
            if(j == 9)break;
        }
    }
    for(i = 0;i < 2;i++){
        for(j = 0;j < 10;j++){
            if(f[i] < ten[i][j]){
                t[i] = s[i];
                s[i] = f[i];
                f[i] = ten[i][j];
                //printf("f %d == %d\n",i,f[i]);
            }
            else if(f[i] >= ten[i][j] && s[i] < ten[i][j]){
                t[i] = s[i];
                s[i] = ten[i][j];
                //printf("s %d == %d\n",i,s[i]);
            }
            else if(s[i] >= ten[i][j] && t[i] < ten[i][j]){
                t[i] = ten[i][j];
                //printf("t %d == %d\n",i,t[i]);
            }
        }
    }
    //printf("f0-%d s0-%d t0-%d f1-%d s1-%d t1-%d\n",f[0],s[0],t[0],f[1],s[1],t[1]);
    printf("%d %d\n",f[0] + s[0] + t[0],f[1] + s[1] + t[1]);


    return 0;
}

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



string reverse(string s) {
  string t = s;
  for (int i = 0;i<s.size();i++) {
    t.at(i) = s.at(s.size() - 1 - i);
  }
  return t;
}

int main() {
  string s;
  cin >> s;
  int Q;
  cin >> Q;
  string left,right;
  bool gyaku = false;
  for (int i = 0;i<Q;i++) {
    int t;
    cin >> t;
    if (t == 1) gyaku = !gyaku;
    else {
      int f;
      cin >> f;
      string c;
      cin >> c;
      if (((f == 1) && !gyaku) || ((f == 2) && (gyaku))) left = c + left;
      else right = right + c;
    }
  }
  if (gyaku) {
    cout << reverse(right) << reverse(s) << reverse(left) << endl;
    
  }
  else cout << left << s << right << endl;
  
}


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

using namespace std;

int main() {
 string s,t ;
  cin >> s >> t;
  for(int i = 0; i < s.size(); i++) {
    if(s[i] != t[i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  
  return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
using ll = long long;
ll n, a, b, k;
const int maxn = 4e5 + 10;
ll f[maxn];
ll inv[maxn];
void init() {
    inv[0] = 1;
    f[0] = 1;
    inv[1] = 1;
    for (ll i = 1; i <= n; i++) {
        f[i] = f[i-1] * i % mod;
    }
    for (ll i = 2; i <= n; i++) {
        inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
    }
    inv[0]=1;
    for(ll i=1;i<=n;i++){
        inv[i]=inv[i-1]*inv[i]%mod;
    }
}
 
bool check(ll num) {
    return num < 0 || num > n;
}
ll c(ll a, ll b) {
    return f[a] * inv[b] % mod * inv[a-b] % mod;
}
ll gao(ll x, ll y) {
    return c(n, x) * c(n, y)% mod;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b >> k;
    init();
    ll ans = 0;
    for (ll i = 0; i <= n; i++) {
        ll sub = k - i * a;
        if (sub % b) continue;
        ll j = sub / b;
        if (check(i)||check(j)) continue;
        ans = (ans + gao(i, j)) % mod;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 6400
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
#pragma warning(disable: 4996)
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;

int a[13][13];

int main() {

	ll n, m, x;

	cin >> n >> m >> x;

	vector<int> c(n);

	rep(i, n) {
		cin >> c[i];
		rep(j, m)cin >> a[i][j];
	}

	ll num = 100000000000;
	ll xS = -1;
	bool fn = false;


	rep(i, 1 << n) {
		ll en = 0;
		vector<int> f(m);
		rep(j, n) {
			if (i >> j & 1) {
				en += c[j];
				rep(k, m) {
					f[k] += a[j][k];
				}
			}
		}

		bool ok = true;
		rep(j, m)if (f[j] < x)ok = false;

		if (ok) { fn = true; if (num > en)num = en; }

	}

	if (fn)cout << num << endl;
	else cout << "-1" << endl;

	return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n;
  cin>>n;
  int a[n];
  rep(i,n) cin>>a[i];
  map<int, int> m;
  rep(i,n) {
    m[a[i]]++;
  }
  ll ans = 1;
  rep(i,n) {
    if(n % 2 == 0) {
      if(i % 2 == 1 && m[i] != 2) {
        cout << 0 << endl;
        return 0;
      }
    } else {
      if(i == 0 && m[i] != 1) {
        cout << 0 << endl;
        return 0;
      } else if(i != 0 && i % 2 == 0 && m[i] != 2) {
        cout << 0 << endl;
        return 0;
      }
    }
  }
  rep(i, n / 2) {
    ans = ans * 2 % MOD;
  }
  cout << ans << endl;

  return 0;
}


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

int main() {
    int n, y;
    cin >> n >> y;
    int a = -1, b = -1, c = -1;
    for (int i=0; i<=n; i++) {
        for (int j=0; i+j<=n; j++) {
            int k = n - i - j;
            if (10000 * i + 5000 * j + 1000 * k == y) {
                a = i; b = j; c = k;
            }
        }
    }
    cout << a << " " << b << " " << c << endl;
    return 0;
}

Measured memory_bytes: 3592
#include<stdio.h>
#include<string.h>
 
int main(){
	char s[11];
    char t[12];
    int i;
    
    scanf("%s", s);
    scanf("%s", t);
    for(i=0; i<strlen(s); i++){
    if(s[i]!=t[i]){
			printf("No");
            return 0;
    	}	
    }
    printf("Yes");
	return 0;    
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;i++)
ll gcd(ll a,ll b){
  if(b==0) return a;
  return gcd(b,a%b);}

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

int main(){
  int n;cin >> n;
  ll t[110];for(int i=0;i<n;i++)cin >> t[i];
  ll x=1;
  rep(i,n) x=lcm(x,t[i]);
  cout << x << endl;}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountl
#define m_p make_pair
#define inf 1000000000000000000
#define MAXN 1000001
#define eps 0.0000000001
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T>//usage rand<long long>()
T rand() {
    return uniform_int_distribution<T>()(rng);
}

// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();

//////////////

#define S second
#define F first
#define int long long  

//////////

signed main()
{
    fastio;
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
    }
    int ans=a[0];
    for(int i=1;i<n;++i)
    {
        ans=__gcd(ans,a[i]);
    }
    cout<<ans;
}

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

int main() {
  int N , A;
  cin >> N >> A;
  
  if (N >= 500 && N % 500 <= A)
    cout << "Yes" << endl;
  if (N >= 500 && N % 500 > A)
    cout << "No" << endl;
  if (N < 500 && N <= A)
    cout << "Yes" << endl;
  if (N < 500 && N > A)
    cout << "No" << endl;
 
}


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

const int N=2e5+5;
const int mod=998244353;
int n,m,l[N],r[N],dp[N],s[N];

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>l[i]>>r[i];
    dp[1]=1;
    s[1]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int left=max(i-r[j],1ll);
            int right=i-l[j];
            if(right>=1) dp[i]=(dp[i]+s[right]-s[left-1]+mod)%mod;
        }
        s[i]=(s[i-1]+dp[i])%mod;
    }
    cout<<dp[n];
}


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


#define x_ real()
#define y_ imag()
#define cross(a, b) (conj(a)*(b)).imag()
#define dot(a, b) (conj(a)*(b)).real()
#define PI acos(-1)
#define F first
#define S second
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define fileIO freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef complex<ld> point;
typedef tuple<int, int, int> line;
typedef vector<point> polygon;
typedef pair<double, double> pd;
pair<int, int> dirs[] = { {1, 2}, {-1, 2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, -2}, {-1, -2} };
ll mod = 1e9 + 7;
ld eps = 1e-6;

ll dp[107][10007][2];

string k;
int d;


ll solve(ll m, int index, bool greater) {
	if (index == (int)k.size()) {
		return m == 0;
	}
	if (dp[m][index][greater] != -1)
		return dp[m][index][greater];

	ll sum = 0;
	if (greater) {
		for (int i = 0; i < 10; i++) {
			sum += solve((m+i) % d, index+1, 1) % mod;
			sum %= mod;
		}
	}
	else {
		for (int i = 0; i < k[index] - '0'; i++) {
			sum += solve((m+i) % d, index+1, 1) % mod;
			sum %= mod;
		}
		sum += solve((m+k[index] - '0') % d, index+1, 0) % mod;
		sum %= mod;
	}

	return dp[m][index][greater] = sum;

}


int main() {
	fastIO;
	cin >> k >> d;
	memset(dp, -1, sizeof dp);
	cout << (solve(0, 0, 0) - 1 + mod) % mod;
}


Measured memory_bytes: 17792
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define ii pair<int, int>
#define vii vector<ii>
#define vvi vector<vi>
#define vvii vector<vii>
#define ld long double
#define iii tuple<int, int, int>
#define sc scanf
#define pb push_back
#define FOR for(int i=1; i<=n; ++i)

int main() {

    string s;
    cin>>s;

    int r = 0;

    if(s[0] == 'R' && s[1] == 'R' && s[2] == 'R') {
        r = 3;
    }
    else if(s[0] == 'R' && s[1] == 'R') {
        r = 2;
    }
    else if(s[1] == 'R' && s[2] == 'R') {
        r = 2;
    }
    else if(s[0] == 'R' || s[1] == 'R' || s[2] == 'R') {
        r = 1;
    }
    printf("%d\n", r);
}



Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N;
    cin >> N;
    vector<int> v(N, 0);
    for (int i = 2; i <= N; i++) {
        int A;
        cin >> A;
        A--;
        v[A]++;
    }
    for (int i = 0; i < N; i++) {
        cout << v[i] << endl;
    }
}

Measured memory_bytes: 3984
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const ll INF=1e+18;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//省略
using vi  = vector<int>;
using vii = vector<vector<int>>;
using vl  = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(){
    ll N,M;
    cin>>N>>M;
    vl X(N);
    REP(i,N) cin>>X[i];
    map<ll,ll> mp1;
    map<ll,pair<ll,ll>> mp2;
    
    //初期化
    REP(i,N){
        mp1[X[i]]++;
    }
    
    for(auto itr=mp1.begin();itr!=mp1.end();itr++){
        ll x=itr->first;
        ll val=itr->second;
        ll key=x%M;
   		
        // val_p:ペアの数 val_amari:あまり
        ll val_p=val/2;
        ll val_amari=val-val_p*2;
        mp2[key].first+=val_p;
        mp2[key].second+=val_amari;
    }

    ll ans=0;
    ll tmp=0;
	ll cnt=0;
    for(auto itr=mp2.begin();itr!=mp2.end();itr++){
      	
        ll x1=itr->first;
        ll p1=itr->second.first;
        ll amari1=itr->second.second;
        ll num1=2*p1+amari1;

        ll x2=(M-x1)%M;

        if(!mp2.count(x2)){
            tmp+=p1;
        }else{
            ll p2=mp2[x2].first;
            ll amari2=mp2[x2].second;
            ll num2=2*p2+amari2;
            if(x1==x2){
                tmp+=(num1/2);
            }else{
                if(num1<num2){
                    swap(p1,p2);
                    swap(amari1,amari2);
                    swap(num1,num2);
                }

                //少ない方の全部を使ってペアを作る
                ans+=num2;
                amari1-=num2;

                //多い方の残りでできるだけペアを作る
                if(amari1<0){
                    p1-=((abs(amari1)+1)/2);
                }
                
                ans+=p1;
            }
        }
    }
    ans/=2;
    ans+=tmp;
    cout<<ans<<endl;
    
}

Measured memory_bytes: 16400
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, A, B;
  int result = 0;
  cin >> N >> A >> B;
  for (int i=1; i<N+1; i++) {
    int sum = 0;
    int remainder1 = i % 10;
    int division1 = i / 10;
    sum += remainder1;
    int remainder2 = division1 % 10;
    int div2 = division1 / 10;
    sum += remainder2;
    int rem3 = div2 % 10;
    int div3 = div2 / 10;
    sum += rem3;
    int rem4 = div3 % 10;
    int div4 = div3 /10;
    sum += rem4;
    sum += div4;
    
    if (sum >= A && sum <= B) {
      result += i; 
    }
  }
  cout << result << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    int N,A,B;
    cin >> N >> A >> B;
    cout << min( N*A, B ) << endl;
    
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python

def main():
    a, b, c = map(int, input().split())
    k = int(input())
    cnt = 0

    while a >= b:
        b *= 2
        cnt += 1
    while b >= c:
        c *= 2
        cnt += 1

    if cnt <= k:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()


Measured memory_bytes: 9164