akhauriyash/Code-Regression huggingface dataset:
/*..............IN THE NAME OF ALLAH.............*/
/**
*     => Md. Sajjat Hosen
*     => Department of Computer Science and Engineering
*     => Bangabandhu Sheikh Mujibur Rahman Science and Technology University
**/

/*..................! TRY ONCE MORE !..................*/

/*...Part - 01...*/

#include <bits/stdc++.h>
using namespace std ;

/*...Part - 02...*/

typedef long long               ll ;
typedef long double             ld ;
typedef unsigned long long      ull ;
typedef pair<int,int>           pii ;
typedef pair<ll,ll>             pll ;
typedef vector<int>             vi ;
typedef vector<ll>              vll ;
typedef vector<vector<int>>     vvi ;

int Int(){int x ; scanf("%d",&x) ; return x ;}
ll Long(){ll x ; scanf("%lld",&x) ; return x ;}
float Float(){float x ; scanf("%f",&x) ; return x ;}
double Double(){double x ; scanf("%lf",&x); return x;}

/*...Part - 03...*/
/*....Debugger....*/

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ' ;
    err(++it, args...);
}

/*...Part - 04...*/
/*...Needed to change according to problem requirements...*/

const int N          = (int)2e5 + 5 ;
const int maxN       = (int)1e6 + 6 ;
const ll  Mod        = (ll)1e9 + 7 ;
const int inf        = (int)2e9 ;
const ll  Inf        = (ll)1e18 ;

/*..........................................................*/
/*...Part - 05...*/

#define     debug(x)    cerr << #x << " = " << x << '\n' ;
#define     rep(i,b,e)  for(__typeof(e) i = (b) ; i != (e + 1) - 2 * ((b) > (e))  ; i += 1 - 2 * ((b) > (e)))
#define     Int         Int()
#define     Long        Long()
#define     Float       Float()
#define     Double      Double()
#define     all(x)      x.begin() , x.end()
#define     sz(x)       (int)x.size()
#define     ff          first
#define     ss          second
#define     pb          push_back
#define     eb          emplace_back
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)

/*...Part - 06...*/
/*...... ! Code start from here ! ......*/



inline void Yes(){printf("Yes\n");}
inline void No(){printf("No\n");}
inline void YES(){printf("YES\n");}
inline void NO(){printf("NO\n");}

int main(){
    //freopen("input.txt","r",stdin);
    int test = 1 , tc = 0 ;
    char s[5];
    int a, b;
    while(test--){
        a = 0;
        b = 0;
        scanf("%s", s);
        for(int i = 0; i < 3; i++){
            if(s[i] == 'A')
                a++;
            else
                b++;
        }
        if(a > 0 and b > 0)
            Yes();
        else
            No();
    }
    return 0 ;
}

/*...Always look at the part - 04...*/
/*...............END................*/

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#include<ctime>

using namespace std;

template <typename T>

inline T read()
{
	T x=0,f=1;char c=getchar();
	while(!isdigit(c))
	{if(c=='-') f=-f;c=getchar();}
	while(isdigit(c))
	{x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint

const int inf=1e9+1e7;

int n,k,s;

int main(void)
{

	// freopen("testdata.in","r",stdin);
	// freopen("testdata.out","w",stdout);

	scanf("%d%d%d",&n,&k,&s);

	for(int i=1;i<=k;i++)
		printf("%d ",s);

	if(s==(int)1e9)
	{
		for(int i=k+1;i<=n;i++)
			printf("1 ");
	}
	else{
		for(int i=k+1;i<=n;i++)
			printf("1000000000 ");
	}

	cout<<endl;

	return 0;

}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    string s,t;
    cin >> s >> t;
    int n = s.size();
    map<char,vector<int>> m;
    rep(i,n) m[s[i]].push_back(i);
    rep(i,n) m[s[i]].push_back(i+n);
    
    ll ans = 0;
    int idx = -1;
    rep(i, t.size()) {
        char c = t[i];
        if(m.count(c) == 0) {
            cout << -1 << endl;
            return 0;
        }
        auto idx_itr = lower_bound(m[c].begin(), m[c].end(), idx+1);
        idx = *idx_itr;
        if(idx >= n) {
            idx -= n;
            ans += n;
        }
    }
    ans += idx+1;
    cout << ans << endl;
}


Measured memory_bytes: 4616
def read_adj_list(n):
    al = [None for _ in range(n + 1)]
    for _ in range(n):
        u, _, *v = (int(x) for x in input().split())
        al[u] = v
    return al


def adj_list_to_matrix(n, al):
    am = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in al[i]:
            am[i][j] = 1
    return am


def print_adj_mat(n, am):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if j > 1:
                print(" ", end="")
            print(am[i][j], end="")
        print()


def main():
    n = int(input())

    adj_list = read_adj_list(n)
    adj_mat = adj_list_to_matrix(n, adj_list)
    print_adj_mat(n, adj_mat)


if __name__ == '__main__':
    main()



Measured memory_bytes: 7096
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  int X;
  cin >> X;
  vector<pair<int, vector<int> > > books(N);

  for(int i=0;i<N;i++){
    int C;
    cin >> C;
    vector<int> algos(M);
    for(int j=0;j<M;j++){
      int A;
      cin >> A;
      algos[j]=A;
    }
    books[i]=make_pair(C,algos);
  }
  long long int minV = INT_MAX;
  for(int i=0;i<(int)pow(2,N);i++) {
    long long int total=0;
    vector<int> A(M,0);
    bool clear=false;
    for(int j=0;j<N;j++){
      if(i&(1<<j)){
        total+=books[j].first;
        for(int k=0;k<M;k++){
          A[k]+=books[j].second[k];
        }
      }
      if(j==N-1){
        clear = (A.size()==count_if(A.begin(), A.end(), [&X](int x){
          return x>=X;
        }));
      }
    }
    if(clear){
      minV = min(minV, total);
    }
  }
  if(minV==INT_MAX) minV = -1;
  cout << minV << endl;
}



Measured memory_bytes: 3960
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

def main():
    N, M, K = map(int, input().split())

    fact = [1]
    for i in range(1, N+3):
        fact.append(fact[-1] * i % MOD)
    def rev(x):
        return pow(x, MOD-2, MOD)
    def cmb(i, k):
        if(i < k): return 0
        return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

    def count(m, k):
        combo = cmb(N-1, k)
        col = m * pow(m-1, N-k-1, MOD)
        val = (combo*col)%MOD
        return val

    cnt = 0
    for k in range(0, K+1):
        addval = count(M, k)
        cnt += addval
        cnt %= MOD

    print(cnt)
if __name__=='__main__':
    main()

Measured memory_bytes: 81920
#include<stdio.h>
int main(void)
{
 int a,b,c,i,x;
 
 x=0;

 scanf("%d %d %d",&a,&b,&c);
 for(i=a;i<=b;i++)
 {
  if(c%i==0)
  {
   x++;
  }
 }
printf("%d\n",x);

return 0;
}


Measured memory_bytes: 2748
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e5 +7;

#include <math.h>
#define PI 3.14159265358979323846264338327950L



int main() {
    int n;
    cin >> n;
    vector<int> a(MOD, 0);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        int n1; cin >> n1;
        a[n1]++;
        sum += n1;
    }
   

    int Q;
    cin >> Q;
    while (Q--) {
        int x, y;
        cin >> x >> y;
        long long total = (long long)a[x] * x;
        sum -= total;
        sum += (long long)a[x] * y;
        a[y] += a[x];
        a[x] = 0;
        cout << sum << "\n";
    }

    return 0;
}

Measured memory_bytes: 3720
import java.util.Scanner;

class Main {
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        String str1 = stdIn.nextLine();

        String str2 = "7";
        int result = str1.indexOf(str2);

        if(result == -1)
            System.out.print("No");
        else
            System.out.print("Yes");
    }

}

Measured memory_bytes: 27012
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <stack>
#include <queue>
#include <list>
#include <iterator>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
	int r, d, x; cin >> r >> d >> x;
	for (int i = 0; i < 10; ++i) {
		x = r * x - d;
		cout << x << endl;
	}

	return 0;
}

Measured memory_bytes: 256
//ITP 1_5_B
#include <iostream>
using namespace std;

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

int main() {
	int h, w;
	while (cin >> h >> w, h) {
		rep(i, h) {
			rep(j, w) {
				if (i == 0 or i == h - 1 or j == 0 or j == w - 1) cout << "#";
				else cout << ".";
			}
			cout << endl;
		}
		cout << endl;
	}
}



Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
#define Endl endl
typedef long long ll;
const int MAXN = (int)2e5 + 5;
ll k, x;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	while (cin >> k >> x)
	{
		for (int i = x - k + 1; i <= x + k - 1; ++i)
			cout << i << ' ';
		cout << endl;
	}
}
/*
3 7
4 0
1 100
*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main()
{
    FASTINOUT;
    ll x,cnt=0;
    cin>>x;
    for (ll i=2; i<=sqrtl(x); i++)
    {
        ll c=0;
        if (x%i==0)
        {
            while (x%i==0)
            {
                c++;
                x/=i;
            }
            ll sum=0,ns=0;
          //  cout<<"c = "<<c<<endl;
            for (ll j=1;; j++)
            {
                sum+=j;
                if (sum==c)
                {
                    ns=j;
                    break;
                }
                else if (sum>c)
                {
                    ns=j-1;
                    break;
                }
            }
            cnt+=ns;
        }
    }
    if (x>1)
        cnt++;
    cout<<cnt<<endl;
    return 0;
}


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

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n), cnt(n+1,0);
    rep(i,n){
        cin >> a[i];
        cnt[a[i]]++;
    }
    ll sum=0;
    for(ll i:cnt){
        sum += i*(i-1)/2;
    }
    rep(i,n){
        ll ans = sum;
        ans -= cnt[a[i]]-1;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 5760
#include <stdio.h>

int cal_gcd(int a,int b){
  int temp,r;

  if(a<b){
    temp=a;
    a=b;
    b=temp;
  }

  while(b!=0){
    r=a%b;
    a=b;
    b=r;
  }

  return a;
}

int main(void){
  int a,b,tgcd,ta,tb;

  while(scanf("%d%d",&a,&b)==2){
    tgcd=cal_gcd(a,b);
    printf("%d ",tgcd);
    ta=a/tgcd;  tb=b/tgcd;
    printf("%d\n",tgcd*ta*tb);
  }

  return 0;
}

Measured memory_bytes: 596
N, M = [int(i) for i in input().split()]
s = [0] * M
c = [0] * M
for i in range(M):
  s[i], c[i] = map(int, input().split())

ans = 1000
for i in range(1000):
  S = str(i)
  if len(S) != N:
    continue
  
  is_ok = True
  for j in range(M):
    if S[s[j]-1] != str(c[j]):
      is_ok = False
      
  if is_ok:
    ans = min(ans, i)

if ans == 1000:
  print(-1)
else:
  print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <cstring>

using namespace std;

int main(){
    string S;
    cin >> S;
    int K=0;

    int f=0,s=1;

    while(true)
    {
        if(f==S.length()){
            break;
        }
        if(f==S.length()-1){
            K++;
            break;
        }
        if(S.at(f)==S.at(f+1)){
            if(f+1 == S.length()-1){
                K++;
                break;
            }else{
                K++;
                f+=2;
                K++;
                f++;
            }
        }else{
            K++;
            f++;
        }
    }
    cout << K << endl;    
    return 0;
}

Measured memory_bytes: 640
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
 
alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");
 
T lread(T = long)()
{
    return readln.chomp.to!T();
}
 
T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}
 
void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}
 
void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}
 
void maxAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) max(dst, src);
}
 
void main()
{
    long a, b, c;
    scan(a, b, c);
    bool B = a <= c && c <= b;
    writeln(B ? "Yes" : "No");
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace At
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadInts();
            if (input[0] + input[1] > 23)
            {
                WriteLine(input[0] + input[1] - 24);
            }
            else
            {
                WriteLine(input[0] + input[1]);
            }
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 11092
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(list(map(int, input()[:-1])))

INF = float('inf')

def is_bipartite_graph():
    team = [0] * N
    valid = True
    q = deque()
    q.append(0)
    team[0] = 1
    while valid and len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if not team[v]:
                    team[v] = team[u]%2 + 1
                    q.append(v)
                else:
                    if (team[v] - team[u])%2 == 0:
                        valid = False
                        break
    return valid


def get_distances(s):
    q = deque()
    q.append(s)
    d = [INF] * N
    d[s] = 0
    while len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                    q.append(v)
    return d


def get_diameter():
    dmax = 0
    for i in range(N):
        d = get_distances(i)
        dmax = max(max(d), dmax)
    return dmax


if is_bipartite_graph():
    print(get_diameter()+1)
else:
    print(-1)


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

typedef long long ll;
int n, ans;

int binary_search(ll k, ll a[]) {
	int l = 0, r = n - 1;
	while (r - l >= 0) {
		ans++;
		int mid = (l + r) / 2;
		if (k == a[mid]) return ans;
		else if (k < a[mid]) r = mid - 1;
		else l = mid + 1;
	}
	return ans;
}
int main() {
	while (cin >> n && n) {
		ans = 0;
		ll k, a[100];
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		sort(a, a + n);
		cin >> k;
		cout << binary_search(k, a) << endl;
	}
}


Measured memory_bytes: 3088
S = input()[::-1]
P = 10**9+7
c = 1
X = [1]+[0]*12
for s in S:
    Y = [0] * 13
    if s == "?":
        for i in range(10):
            for j in range(13):
                Y[(c*i+j)%13] += X[j]
                Y[(c*i+j)%13] %= P
    else:
        for j in range(13):
            Y[(c*int(s)+j)%13] = X[j]
            
    X = Y
    c = c*10%13

print(X[5])

Measured memory_bytes: 43116
#include <iostream>
#include <cstdio>

using namespace std;

int S[100000];

int main(void) {

    int n;
    scanf("%d", &n);
//    cin >> n;

    for (int i = 0; i < n; ++i) {
//        cin >> S[i];
        scanf("%d", S + i);
    }

    int q, total = 0;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int t;
//        cin >> t;
        scanf("%d", &t);
        int left = 0, right = n - 1, mid = 0;
        while (left <= right) {     // '<' ?????¨?????¨??§?????????
            mid = (left + right) / 2;
            if (t > S[mid]) {
                left = mid + 1;
            }
            else if (t < S[mid]) {
                right = mid - 1;
            }
            else {
                ++total;
                break;
            }
        }
    }

    printf("%d\n", total);

    return 0;
}

Measured memory_bytes: 1616
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using P = pair<int,int>;
const long long inf = 1000000001; // const 書き換え禁止
const double PI = 3.14159265358979323846; //M_PI はライブラリ

int main(void){
    int n;
    string s,t;
    cin >> n >> s >> t;
    rep(i,n){
        cout << s[i] << t[i];
    }
    cout << endl;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
   ll r;cin>>r;
   if(r<1200)puts("ABC");
   else if(r<2800)puts("ARC");
   else puts("AGC");
   return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);
    public static void main(String[] args){
	int n = kbd.nextInt();
	while(n>0){
	    solve();
	    n--;
	}
    }

    static void solve(){
	String train = kbd.next();
	String[] part = new String[(train.length()-1)*8];
	String a, b, c, w;
	int i, k=0, cnt=0;

	for(i=1; i<train.length(); i++){
	    a = train.substring(0, i);
	    b = train.substring(i, train.length());
	    //System.out.println(a+" "+b);
	    w = a;

	    c = a+b;        //反転なし
	    if(! isExist(part, c)){
		part[k] = c;
		cnt++; k++;
	    }
	    c = b+a;        //反転なし
	    if(! isExist(part, c)){
		part[k] = c;
		cnt++; k++;
	    }

	    a = reverse(a);
	    c = a+b;        // aのみ反転
	    if(! isExist(part, c)){
		part[k] = c;
		cnt++; k++;
	    }
	    c = b+a;        // aのみ反転
	    if(! isExist(part, c)){
		part[k] = c;
		cnt++; k++;
	    }

	    b = reverse(b);
	    c = w+b;        // bのみ反転
	    if(! isExist(part, c)){
		part[k] = c;
		cnt++; k++;
	    } 
	    c = b+w;        // bのみ反転
	    if(! isExist(part, c)){
		part[k] = c;
		cnt++; k++;
	    }

	    c = a+b;        // a,bともに反転
	    if(! isExist(part, c)){
		part[k] = c;
		cnt++; k++;
	    }
	    c = b+a;        // a,bともに反転
	    if(! isExist(part, c)){
		part[k] = c;
		cnt++; k++;
	    }
	}
	/*
	for(i=0; part[i]!=null; i++){
	    System.out.println(part[i]);
	}
	*/
	System.out.println(cnt);
    }

    static String reverse(String a){
	String[] p = new String[a.length()];
	int i;
	for(i=0; i<a.length(); i++){
	    p[i] = a.substring(i, i+1);
	}
	a = "";
	for(i=p.length-1; i>=0; i--){
	    a += p[i];
	}
	return a;
    }

    static boolean isExist(String[] part, String x){
	int i;
	for(i=0; i<part.length; i++){
	    if(x.equals(part[i])) return true;
	}
	return false;
    }
}

Measured memory_bytes: 88616
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define um map <ll,ll>
#define rep(i,z,n)  for(int i=z;i<n;i++)
#define repi(i,z,n) for(int i=z;i<=n;i++)
#define repn(i,z,n) for(int i=n-1;i>=z;i--)
#define vec vector<ll>
#define vecp vector<pair<ll,ll>>
#define pi (double)3.14159265358979323846
#define ld long double
#define all(z) z.begin(),z.end()

ll power(ll a, ll b, ll m) { ll ans = 1; a = a % m; if (a == 0) return 0; while (b) { if (b & 1) ans = (ans * a) % m; b /= 2; a = (a * a) % m; } return ans; }
ll modInverse(ll a, ll m) {return power(a, m - 2, m);}
ll binpow(ll a, ll b) {ll res = 1; while (b > 0) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll binlog2(ll n) {ll logValue = -1; while (n) {logValue++; n >>= 1;} return logValue;}
ll ceil(ll t1, ll t2) {ll ans = (t1 + t2 - 1) / t2; return ans;}
void print(vec a) {rep(i, 0, a.size())cout << a[i] << " "; cout << endl;}
const ll mod = 998244353;
const ll N = 2e5 + 5;
const ll inf = 2e18;

void solve() {
    ll n, k;
    cin >> n >> k;
    vecp vp(k);
    rep(i, 0, k) {
        cin >> vp[i].F >> vp[i].S;
    }

    vec dp(n, 0);
    dp[0] = 1;
    dp[1] = -1;

    rep(i, 0, n) {
        if (i > 0) {
            dp[i] += dp[i - 1];
            dp[i] %= mod;
        }

        rep(j, 0, k) {
            ll l, r;
            l = vp[j].F;
            r = vp[j].S;
            r++;
            if (i + l < n) {
                dp[i + l] += dp[i];
                dp[i + l] %= mod;
            }

            if (i + r < n) {
                dp[i + r] -= dp[i];
                dp[i + r] += mod;
                dp[i + r] %= mod;
            }
        }
    }

    cout << dp[n - 1] << endl;

}


int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    speed;
    int test = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case #" << t1 << ": ";
        solve();
    }
    return 0;
}

Measured memory_bytes: 4716
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n, w, d;
    using A = array<int, 3>;
    while(cin >> n >> w >> d, n|w|d){
        vector<A> v;
        v.emplace_back(A{-1, -1, 1});
        v.emplace_back(A{0, w, d});
        for (int i = 0; i < n; ++i) {
            int p, c;
            cin >> p >> c;
            int x = v[p][1], y = v[p][2];
            v[p] = {-1, -1, 1};
            c %= 2*(x+y);
            if(c < x){
                v.push_back(A{2*i, min(c, x-c), y});
                v.push_back(A{2*i+1, max(c, x-c), y});
            }else if(c < x+y){
                v.push_back(A{2*i, x, min(c-x, x+y-c)});
                v.push_back(A{2*i+1, x, max(c-x, x+y-c)});
            }else if(c < 2*x+y){
                v.push_back(A{2*i, min(c-x-y, 2*x+y-c), y});
                v.push_back(A{2*i+1, max(c-x-y, 2*x+y-c), y});
            }else {
                v.push_back(A{2*i, x, min(c-2*x-y, 2*x+2*y-c)});
                v.push_back(A{2*i+1, x, max(c-2*x-y, 2*x+2*y-c)});
            }
            sort(v.begin(), v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
        }
        vector<int> ans;
        for (int i = 1; i < v.size(); ++i) {
            ans.emplace_back(v[i][1]*v[i][2]);
        }
        sort(ans.begin(),ans.end());
        for (int i = 0; i < ans.size(); ++i) {
            if(i) cout << " ";
            cout << ans[i];
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 3116
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using static System.Globalization.CultureInfo;

class Program
{
    static void Main(string[] args)
    {
        var str = ReadLine();
        var ct0 = 0;
        var ct1 = 0;
        var res = 0L;
        for(var i=0;i<str.Length;i++)
            if (str[i] == '0')
            {
                if (ct1 > 0)
                {
                    res += 2;
                    ct1--;
                }
                else ct0++;
            }
            else
            {
                if (ct0 > 0)
                {
                    res += 2;
                    ct0--;
                }
                else ct1++;
            }
        WriteLine(res);
    }
}


Measured memory_bytes: 13280
import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args)throws IOException{
         Scanner sc = new Scanner(System.in);
        while(true){
           
        int a = sc.nextInt();
        String op = sc.next();
        int b = sc.nextInt();
        if("+".equals(op)){
            System.out.println(a+b);
        }else if("-".equals(op)){
            System.out.println(a-b);
        }else if("*".equals(op)){
            System.out.println(a*b);
        }else if ("/".equals(op)){
            System.out.println(a/b);
        }else if("?".equals(op)){
            break;
        }
        }
     }
}

Measured memory_bytes: 26384
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;
bool vis[105];
 main()

{
    fast
    int x,n;
    cin>>x>>n;
    f(i,1,n)
    {
        int z;
        cin>>z;
        vis[z]=1;
    }
    int mn=inf,ses;
    f(i,0,101)
    {
        if(vis[i]==0)
        {
             int z=abs(x-i);
             if(z<mn)
             {
                 mn=z;
                 ses=i;
             }
        }
    }
    cout<<ses<<endl;
    return 0;

}





































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

int n, a, b;
vector<int> h; 

bool f(int m){
	int cnt = 0;
	rep(i, 0, n){
		int tmp = h[i] - b * m;
		if(tmp >= 0) cnt += (tmp + a - b - 1) / (a - b);
	}
	return cnt <= m;
}

signed main(){
	cin >> n >> a >> b;
	h.resize(n);
	rep(i, 0, n){
		cin >> h[i];
	}
	int ng = 0, ok = 1e9;
	while(ok - ng > 1){
		int mid = (ok + ng) / 2;
		if(f(mid)) ok = mid;
		else ng = mid;
	}
	cout << ok << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF ((1LL<<61) + (1<<29))
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
ll my_gcd(ll a, ll b) { return b ? my_gcd(b, a%b) : a; };
void _INPUT_IMPL_() {};
template <class T, class... Args> void _INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; _INPUT_IMPL_(args...); }
void _OUTPUT_IMPL_() {};
template <class T, class... Args> void _OUTPUT_IMPL_(T dest, Args... args) { cout<< dest << (sizeof...(Args)?" ":""); _OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; _INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define out(...) (_OUTPUT_IMPL_(__VA_ARGS__), std::cout<<std::endl)
#define set_fix(x) ((std::cerr<<std::fixed<<std::setprecision(x)),(std::cout<<std::fixed<<std::setprecision(x)))
//小さい方に寄る
#define space_op(x, y, a, b, c) ([](auto x_, auto y_, auto a_, auto b_, auto c_){if(x_<y_)return a_;if(x_>y_)return c_;return b_;}(x,y,a,b,c))
#define space_out(x, y, a, b, c) out(space_op(x, y, a, b, c))

int main() {
	in(int, N);
    in_v(ll, H, N);
    ll bef = H[0];
    bool ans = true;
    loop(i, N){
      if(bef > H[i])
        ans = false;
      if(bef == H[i])
        bef = H[i];
      else
        bef = H[i]-1;
    }
	YesNo(ans);
}

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

using namespace std;

string type[2] = {"JPY", "BTC"};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  double total = 0;
  for (int i = 0; i < n; i++) {
    double val;
    string T;
    cin >> val >> T;
    if (T == type[0]) {
      total += val;
    } else {
      total += val * 380000;
    }
  }
  cout << total << '\n';
  return 0;
}

Measured memory_bytes: 3792
n = gets.to_s.to_i
words = Array.new(n){ gets.to_s.chomp.bytes.sort.pack("U*") }

h = Hash.new()
ans = 0
words.each do |s|
  
  if h.has_key?(s)
    ans += (h[s] += 1)
  else
    h[s] = 0
  end
end

puts ans

Measured memory_bytes: 32380
#include <bits/stdc++.h>
#define r(i,n) for(int i = 0; i<n; i++)
using namespace std;
 
int main() {
  char c1,c2;
  cin >> c1 >> c2;
  if(c1=='9'||c2=='9')cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

max_h = max(h_list)

cnt_water = 0
for i in range(1, max_h+1)[::-1]:
    watering = False
    for j in range(n):
        if h_list[j] == i:
            if not watering:
                cnt_water += 1
                watering = True
            h_list[j] -= 1
        else:
            watering = False
print(cnt_water)


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

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

    if (min(B, D) > max(A, C)) {
        cout << min(B, D) - max(A, C) << endl;
    }
    else {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

int main(){
    ll s;
    cin >> s;
    ll a = sqrt(s);
    if(a*a == s){
        cout << "0 0 " << a << " 0 0 " << a << endl;
    }else{
        if(a*a < s) a++;
        ll b = a*a - s;
        cout << "0 0 " << a << " " << 1 << " " << b << " " << a << endl;
    }

    return 0;
}

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

int main() {
  string x;
  cin >> x;
  if(x=="a"||x=="i"||x=="u"||x=="e"||x=="o"){
  cout << "vowel" << endl;
  }
  else{
  cout << "consonant" << endl;
}
}


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


int main(){
  string s;
  cin >> s;
  int n = s.size();
  ll sum=0;
  REP(bit,1<<(n-1)){
    ll t = s[0]-'0';
    REP(i,n-1){
      if (bit&(1<<i)) {
	sum += t;
	t = s[i+1] - '0';
      }
      else {
	t *= 10;
	t += s[i+1] -'0';
      }
    }
    sum+=t;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

#define lli long long int
int c_f(const void *a, const void *b)
{
	return(*(char*)a - *(char*)b);
}

int s_f(const void *a, const void *b)
{
	return(strcmp(*(char **)a, *(char **)b));
}
int main(void)
{
	int n;
	scanf("%d",&n);
	char **s;
	s = (char**)malloc(sizeof(char *)*(n));
	int i = 0;
	int j = 0;
	while (i < n)
	{
		s[i] = (char *)malloc(sizeof(char)*(12));
		j = 0;
		while (j < 12)
		{
			s[i][j] = '\0';
			j++;
		}
		scanf("%s",s[i]);
		qsort(s[i],10,sizeof(char),c_f);
		i++;
	}
	i = 0;
	qsort(s,n,sizeof(char *),s_f);
	//printf("degbug001000\n");
	i = 0;
	j = 0;
	lli cnt = 0;
	lli tmp = 0;
	lli t = 0;
	while (i < n-1)
	{
		j = i+1;
		tmp = 1;
		while (j < n && strcmp(s[i],s[j]) == 0 && j < n)
		{
			//printf("debug:i:%d, j:%d\n",i,j);
			//printf("debug:s_i:%s\n",s[i]);
			//printf("debug:s_j:%s\n",s[j]);
			tmp++;
			j++;
		}
		//printf("debug:cnt:%lld, tmp:%lld\n",cnt,tmp);
		t = tmp -1;
		cnt+=(((1+t)*t)/2);
		i+=tmp;
	}
	printf("%lld\n",cnt);

	return(0);
}



Measured memory_bytes: 4860
# 全点に対してつながってるとしたらsum(N)-自分の値になる
# N=4だと(1: 9, 2:8, 3: 7, 4: 6)
# これをN=3で考えてみる
# (1: 5, 2: 4, 3: 3)
# どうも最小値-1を目指せばできそうな雰囲気がある?
# N=4のときは2-3と1-4を断ち切ることになる
# N=5のとき(1: 14, 2: 13, 3: 12, 4: 11, 5: 10)
# 最小値-1の9を目指してみると構築できない...
# 10を目指してみると構築できる（1-4と2-3を断ち切る）
# N=6のとき(1: 20, 2: 19, 3: 18, 4: 17, 5: 16, 6: 15)
# 14を目指してみると構築できる(1-6, 2-5, 3-4を断ち切る)
# N=7のとき(1: 27: 2: 26, 3: 25, 4: 24, 5: 23, 6: 22, 7: 21)
# 21を目指してみると構築できる(1-6,2-5,3-4を断ち切る)
# どうやら見えちまったようだ
# 全点の辺の数は1+2+...N-2+N-1 = (N-1)*N//2（等差数列の和）、 断ち切る数はn/2

n = int(input())
t = [[True if i != j else False for j in range(n)] for i in range(n)]
edge_sum = n * (n - 1) // 2 - n // 2
for i in range(n // 2):
    t[i][n - i - (1 if n % 2 == 0 else 2)] = False
print(edge_sum)
for i in range(n):
    for j in range(i + 1, n):
        if t[i][j]:
            print(f"{i+1} {j+1}")


Measured memory_bytes: 9332
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

struct edge{lint from,to,cost;};
edge es[200000]; // MAX_E
lint d[200000]; // MAX_V
int V,E;
int roop=0;
bool check=true;
lint save;

void bellmanford(int S){
  fill(d,d+V,LINF);
  d[S]=0;
  while(true){
    bool update=false;
    rep(i,E){
      edge e=es[i];
      if(d[e.from]!=LINF && d[e.to]>d[e.from]+e.cost){
        d[e.to]=d[e.from]+e.cost;
        update=true;
      }
    }
    if(!update) break;
    roop++;
    if(roop==V-1) save=d[V-1];
    if(roop==2*V){
      if(save!=d[V-1]) check=false;
      break;
    }
  }
}

int main(void){
  cin >> V >> E;
  rep(i,E){
    edge in;
    cin >> in.from >> in.to >> in.cost;
    in.cost*=-1;
    in.from--,in.to--;
    es[i]=in;
  }
  bellmanford(0);
  if(check) cout << d[V-1]*-1 << endl;
  else cout << "inf" << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)n; i++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
typedef long long unsigned int ll;
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<ll > a(n);
  vector<ll > sum(n, 0);
  REP(i, n){
    cin >> a[i];
  }
  sum[0] = a[0];
  REP(i, n - 1){
    sum[i + 1] = sum[i] + a[i + 1];
  }


  ll ans = ULLONG_MAX;

  ll b = 0;
  ll c = 0;
  ll tmp = 0;
  for(int i = 0; i < n - 1; i ++ )
  {
    b = sum[i];
    c = sum[n - 1] - b;
    if(b == c){
      ans = 0;
      break;
    }else if(b < c){
      tmp = c - b;
    }else{
      tmp = b - c;
    }
    ans = min(ans, tmp);
  }


  cout << ans << endl;
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    cin >> N;
    vector<pair<ll, ll>> D(N);
    rep(i, N) cin >> D[i].first >> D[i].second;
    rep(i, N - 2) {
        if(D[i].first == D[i].second && D[i + 1].first == D[i + 1].second && D[i + 2].first == D[i + 2].second) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


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

#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;

int main() {
    string S; cin >> S;
    cout << S.substr(0,3) << endl;

    return 0;
}


Measured memory_bytes: 3628
n = int(input())

count = 0
ans = False
for i in range(n):
    d1, d2 = map(int, input().split())
    if d1 == d2:
        count += 1
    else:
        count = 0

    if count == 3:
        ans = True
        break

print('Yes') if ans else print('No')


Measured memory_bytes: 9164
#include<stdio.h>
#include <iostream>
#include <string.h>
#include <cstdlib>

using namespace std;

#define BUF_SIZE 1024

struct Node{
	int data;
	Node* prev;
	Node* next;
};

class ConnectedList{
public:
	ConnectedList(){
		motherNode = new Node();
		motherNode->data = -1;
		motherNode->prev = motherNode;	
		motherNode->next = motherNode;
	};
	~ConnectedList(){
		Node* tmpNode = motherNode->next;
		Node* nextNode;
		while(tmpNode != motherNode){
			nextNode = tmpNode->next;
			delete tmpNode;
			tmpNode = nextNode;
		}
		delete motherNode;
	};
	void insertNode(int x){
		Node* tmpNode = motherNode->next;
		motherNode->next = new Node();
		motherNode->next->data = x;
		motherNode->next->next = tmpNode;
		motherNode->next->prev = motherNode;
		tmpNode->prev = motherNode->next;
	};
	void deleteNode(int x){
		Node* tmpNode = motherNode->next;
		while(tmpNode != motherNode && tmpNode->data != x){
			tmpNode = tmpNode->next;
		}
		if(tmpNode != motherNode){	
			tmpNode->prev->next = tmpNode->next;
			tmpNode->next->prev = tmpNode->prev;
			delete tmpNode;
		}
	};

	void deleteFirst(){
		Node* tmpNode = motherNode->next;
		motherNode->next = motherNode->next->next;
		motherNode->next->prev = motherNode;
		delete tmpNode;	
	};

	void deleteLast(){
		Node* tmpNode = motherNode->prev;
		motherNode->prev = motherNode->prev->prev;
		motherNode->prev->next = motherNode;
		delete tmpNode; 
	};

	void showList(){
		Node* tmpNode = motherNode->next;
		printf("%d",tmpNode->data);
		tmpNode = tmpNode->next;
		while(tmpNode != motherNode){
			printf(" %d",tmpNode->data);
			tmpNode = tmpNode->next;
		}
		printf("\n");
	}

private:
	Node* motherNode;
};


int main(){

	char buf[BUF_SIZE];
	int n = atoi(fgets(buf,BUF_SIZE,stdin));

	ConnectedList list;

	for(int i = 0; i < n; i++){

		fgets(buf,BUF_SIZE,stdin);

		if(buf[6] == 'F'){
			list.deleteFirst();
		}else if(buf[6] == 'L'){
			list.deleteLast();
		}else{
			int S = 0;
			
			if(buf[0] == 'i'){	//insert x

				for(int i = 0; buf[i] != '\0';i++){
					if(buf[i] >= '0' && buf[i] <= '9'){
						S = 10*S + (buf[i] - '0');
					}
				}
				list.insertNode(S);
			}else{	
				for(int i = 0;buf[i] != '\0';i++){
					if(buf[i] >= '0' && buf[i] <= '9'){
						S = 10*S + (buf[i] - '0');
					}
				}
				list.deleteNode(S);
			}

		}

	}

	list.showList();

}



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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<string> vec(3);
  	for (int i = 0; i < 3; i++) {
    	cin >> vec[i];
    }
  	string res = "";
  	for (int i = 0; i < 3; i++) {
    	res += vec[i][i];
    }
  	cout << res << '\n';
    return 0;
}


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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


class UnionFind{
    public:
        UnionFind(int N) : parent(N), rank(N){
            for(int i = 0; i < N; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        int find(int n){
            if(parent[n] == n){
                return n;
            }
            return parent[n] = find(parent[n]);
        }

        void merge(int m, int n){
            int root_x = find(m);
            int root_y = find(n);
            if(root_x == root_y){
                return;
            }
            if(rank[root_x] < rank[root_y]){
                parent[root_x] = root_y;
            }else if(rank[root_x] > rank[root_y]){
                parent[root_y] = root_x;
            }else{
                parent[root_y] = root_x;
                rank[root_x]++;
            }
        }

        bool equivalent(int x, int y){
            return find(x) == find(y);
        }

    private:
        vector<int> parent;
        vector<int> rank;

};

int N, M;
int X[100000];
priority_queue<pint, vector<pint>, greater<pint>> que;

signed main(){
    cin >> N >> M;
    REP(i, M) cin >> X[i];
    sort(X, X + M);
    REP(i, M - 1){
        que.push(pint(X[i + 1] - X[i], i));
    }
    UnionFind uf(M);
    int uf_size = M, sum = 0;
    while(uf_size > N){
        pint t = que.top();
        sum += t.first;
        if(!uf.equivalent(t.second, t.second + 1)) uf_size--;
        uf.merge(t.second, t.second + 1);
        que.pop();
    }
    PRINT(sum);
    return 0;
}

Measured memory_bytes: 2164
#include<stdio.h>

int main(void)
{
	int n,m,i,j,x;
	int a[100][100];
	int b[100];
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	for(i=0;i<m;i++)
	{
		scanf("%d",&b[i]);
	}
	for(i=0;i<n;i++)
	{
		x = 0;
		for(j=0;j<m;j++)
		{
			x += a[i][j] * b[j];
		}
		printf("%d\n",x);
	}
	return 0;
}

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

int main(){
  long long int i,n,m,fib[100002],kotae=1;
  fib[0]=0;
  fib[1]=1;
  for(i=2;i<100002;i++){
    fib[i]=(fib[i-1]+fib[i-2])%1000000007;
  }
  cin>>n>>m;
  int a[m+1];
  a[0]=-1;
  for(i=1;i<m+1;i++){
    cin>>a[i];
    kotae=(kotae*(fib[a[i]-a[i-1]-1]))%1000000007;
  }
  kotae*=fib[n-a[m]];
  cout<<kotae%1000000007;
}

Measured memory_bytes: 1408
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static int modP = 1000000007;

	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			long[] a = in.nextLongArray(n);
			long[] sum = new long[n+1];
			for (int i = 1; i < n+1; i++) {
				sum[i] = sum[i-1] + a[i-1];
			}

			Map<Long,Integer> map = new HashMap<>();
			long ans = 0;
			for (int i = 0; i < n+1; i++) {
				if (map.containsKey(sum[i])) {
					 ans += map.get(sum[i]);
					 map.put(sum[i], map.get(sum[i])+1);
				} else {
					map.put(sum[i], 1);
				}
			}

			out.println(ans);
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}


Measured memory_bytes: 53708
# B
N = int(input())
P_list = []
Q_list = [0]*(N+1)
for i in range(1, N+1):
    p = int(input())
    Q_list[p] = i
    
straight = 1
max_straight = 1
for i in range(1, N):
    if Q_list[i] < Q_list[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1
        
print(N - max_straight)

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

using namespace std;

const int MAXN = 1e7 + 10;

int n, T, k, m;

int a[MAXN], b[MAXN], c[MAXN];

int dp[MAXN][3];

string s, t;

const int MOD = 1e9 + 7;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i] >> c[i];
    
    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];

    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][1] + a[i], dp[i - 1][2] + a[i]);
        dp[i][1] = max(dp[i - 1][0] + b[i], dp[i - 1][2] + b[i]);
        dp[i][2] = max(dp[i - 1][0] + c[i], dp[i - 1][1] + c[i]);
    }
    
    cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));
}


Measured memory_bytes: 5932