akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class Solve {
public:
    void solve() {
        Int N;
        cin >> N;
        vector<Int> S(N);
        bool flag = true;
        for (int i = 0; i < N; ++i) {
            cin >> S[i];
            if (S[i] % 2 == 0) {
                if(S[i] % 3 && S[i] % 5){
                    flag = false;
                }
            }
        }
        if(flag){
            cout << "APPROVED" << endl;
        }else{
            cout << "DENIED" << endl;
        }



    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


Measured memory_bytes: 256
n, a, b, c, d = map(int,input().split())
s = str(input())

ans = 'Yes'
if '##' in s[a-1:c] or '##' in s[b-1:d]:
    ans = 'No'

if ans == 'Yes':
    if c<d:
        pass
    else:
        if '...' in s[b-2:d+1]:
            pass
        else:
            ans = 'No'

print(ans)


Measured memory_bytes: 40816
def main():
    num = int(input())
    data = list(input())
    soppo = data.count('E')

    ans = num

    for i in range(num):
        now_person = data[i]
        kari = soppo
        if now_person == 'E':
            kari -= 1

        if kari < ans:
            ans = kari

        if now_person == 'E':
            soppo -= 1
        else:
            soppo += 1

    print(ans)



if __name__ == '__main__':
    main()


Measured memory_bytes: 64112
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;
import std.container;

alias sread = () => readln.chomp();
long bignum = 1_000_000_007;

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

auto manhattan(long x1, long y1, long x2, long y2)
{
    return abs(y2 - y1) + abs(x2 - x1);
}

void main()
{
    auto n = lread();
    auto transport = new long[](5);
    foreach (i; 0 .. 5)
    {
        transport[i] = lread();
    }
    auto minimam = transport.reduce!(min);
    auto most = (n + (minimam - 1)) / minimam;
    writeln(most + 4);
}


Measured memory_bytes: 256
def main():
    n, m, d = map(int, input().split())
    ans = 0
    if d == 0:
        ans = (m - 1) / n
    else:
        ans = 2*(m - 1) * (n - d) / (n ** 2)
    print(ans)


if __name__ == '__main__':
    main()


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

ll n,l,ans=0;
ll a[maxn];

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}

inline void writ(ll x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) writ(x/10);
	putchar(x%10+'0');
}
inline void write(ll x){writ(x);putchar('\n');}

int main()
{
	n=read();
	l=1;
	for (int i=1;i<=n;++i) a[i]=read();
	ll ww=0;
	for (int i=1;i<=n;++i)
	{
		while ((ww^a[i])^(ww+a[i])) ww-=a[l],++l;
		ww+=a[i];
		ans+=i-l+1;
	}
	write(ans);
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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(){
    int w, a, b; cin >> w >> a >> b;

    if(a+w < b) cout << b - a - w << endl;
    else if(b+w < a) cout << a - b - w << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 256
H,W = map(int,input().split())
candidate = []

for h in range(1,H):
    l = H-h
    cand1 = [h*W]
    cand2 = [h*W]
    cand1.append(l//2*W)
    cand1.append((l-l//2)*W)
    cand2.append(l*(W//2))
    cand2.append(l*(W-W//2))
    candidate.append(max(cand1)-min(cand1))
    candidate.append(max(cand2)-min(cand2))

for w in range(1,W):
    l = W-w
    cand1 = [H*w]
    cand2 = [H*w]
    cand1.append(H*(l//2))
    cand1.append(H*(l-l//2))
    cand2.append(l*(H//2))
    cand2.append(l*(H-H//2))
    candidate.append(max(cand1)-min(cand1))
    candidate.append(max(cand2)-min(cand2))
    
        

print(min(candidate))
    

Measured memory_bytes: 18864
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7;

int main()
{
	IO_OP;
	
	int H, W, h, w;
	cin >> H >> W >> h >> w;
	cout << H * W - (h*W + w*H) + h*w << endl;
	
}



Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {

      
 public static void main(String[] args) {
    
    Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    int H = in.nextInt();
    int W = in.nextInt();
    in.nextLine();
    //System.out.println(" h "+H+ " W "+W);
    char[][] arr = new char[H][W];
    int[][] dp = new int[H][W];
    int mod = (int)(1e9 + 7);
    
    for(int i = 0; i < H; i++) {
         arr[i] = in.nextLine().toCharArray();
    }
    
    for(int i = 1; i < W; i++) {
        if(arr[0][i] == '.') {
            dp[0][i] = 1;
        }
        else {
            break;
        }
    }
    
    for(int j = 1; j < H; j++) {
        if(arr[j][0] == '.') {
            dp[j][0] = 1;
        }
        else {
            break;
        }
    }
    
    for(int i = 1; i < H; i++) {
        for(int j = 1; j < W; j++) {
            if(arr[i][j] == '.') {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
            }
        }
    }
    
    System.out.println(dp[H-1][W-1]);
    
  }
  
  
}

Measured memory_bytes: 48424
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  long long int(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<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>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

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

#define P pair<int,int>
#define V vector<int>
#define S set<int>
#define pb(v) push_back(v)
int main(){
    CIN(N);CIN(L);
    vector<string> vec;
    REP(a,N){
        string s;cin >>s;
        vec.pb(s);
    }
    sort(ALL(vec));
    REP(a,N){
        cout<<vec.at(a);
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))

int
main(int argc, char *argv[])
{
  int n, q;
  scanf("%d %d", &n, &q);
  char s[100001];
  scanf("%s", s);
  int ac[100000] = {};
  for(int i = 1; i < n; ++i){
    ac[i] = ac[i - 1];
    if(s[i - 1] == 'A' && s[i] == 'C'){
      ac[i]++;
    }
  }
  int r, l;
  for(int i = 0; i < q; i++){
    scanf("%d %d", &r, &l);
    printf("%d\n", ac[l - 1] - ac[max(r - 1, 0)]);
  }
  return 0;
}


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


int main() {
    int num;
    cin >> num;
    if (num < 1200) {
        cout << "ABC" << endl;
    } else if (num < 2800) {
        cout << "ARC" << endl;
    } else {
        cout << "AGC" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int d, i, n;
	scanf("%d", &n);
	int num[n];
	i = 0;
	while (scanf("%d", &d) == 1) {
		num[i] = d;
		i ++;
	}
	for (i = n - 1; i >= 1; i --) {
		printf("%d ", num[i]);
	}
	printf("%d\n", num[0]);
	return 0;
}

Measured memory_bytes: 596
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int N, A, B, C;

signed main() {
    cin >> N >> A >> B >> C;

    vector<int> vec(N);
    for(int i=0; i<N; i++) {
        cin >> vec[i];
    }

    int pw = 1;
    for(int i=0; i<N; i++) {
        pw *= 4;
    }

    int ans = INF;
    for(int bit=0; bit<pw; bit++) {
        int rem = bit;
        vector<int> sel;
        for(int i=0; i<N; i++) {
            sel.push_back(rem % 4);
            rem /= 4;
        }

        int MP = 0;
        vector<int> sum(3);
        for(int i=0; i<N; i++) {
            if(sel[i] == 3) continue; // つかわない
            if(sum[ sel[i] ] > 0) MP += 10;
            sum[ sel[i] ] += vec[i];
        }

        MP += abs(A - sum[0]);
        MP += abs(B - sum[1]);
        MP += abs(C - sum[2]);

        bool valid = true;
        for(int i=0; i<3; i++) {
            valid &= (sum[i] > 0);
        }
        if(!valid) continue;
        chmin(ans, MP);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
  
  string S;	cin >> S;
  int ca = 0, cb = 0, cc = 0;
  for(int i = 0 ; i < 3 ; i++){
	if(S[i] == 'a')	ca += 1;
    else if(S[i] == 'b') cb += 1;
    else 			cc += 1;
  }
  
  if(ca && cb && cc)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  
  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


n = I()
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = LI()
    G[u] += [v]
    G[v] += [u]


ret = 0
for jj in range(1, n + 1):
    ret += jj * (n - jj + 1)


for i in range(n):
    for v in G[i + 1]:
        if v > i:
            ret -= (n - v + 1) * (i + 1)

print(ret)


Measured memory_bytes: 109240
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int dp[11010];
int match[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int A[10];
    rep(i, 10010) dp[i] = -INF;
    dp[0] = 0;
    rep(i, M) cin >> A[i];
    sort(A, A + M, greater<int>());
    rep(i, M) dp[match[A[i]]] = 1;
    rep(i, N) {
        rep(j, M) {
            dp[i + match[A[j]]] = max(dp[i + match[A[j]]], dp[i] + 1);
        }
    }
    //rep(i, N + 1) cout << i << " " << dp[i] << endl;
    string ans;
    while(N > 0) {
        rep(j, M) {
            if (N - match[A[j]] >= 0 && dp[N] == dp[N - match[A[j]]] + 1) {
                ans += (char)(A[j] + '0');
                N -= match[A[j]];
                break;
            }
        }
        //cout << ans << " " << N << endl;
    }
    cout << ans << endl;
    


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const int INF = +100100100;
typedef pair<int,int> P;
const ll MO = 1000000007;

int main(){
    ll n;
    cin >> n;
    ll ans=0;    
    int r = (18-log10(2))/(1-log10(2));
    if(n%2==0){
        rrep(i,r){
            ll div = 2*pow(5,i);
            ans += n/div;
        }
    }else{
        cout << 0 << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <functional>
#include <numeric>
#include <sstream>

#define REP(i, n) for(int i = 0;i < (n); i++)
#define REP2(i, x, n) for(int i = (x); i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1;i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

#define LL long long int
#define LD long double

#define PI 3.14159265358979

using namespace std;

//================================================

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

	int N;
	cin >> N;
	cin.ignore();

	string from = "Hoshino";
	REP(i, N) {
		string S;
		getline(cin, S);

		while(true) { 
			int res = S.find("Hoshino", 0);
			if (res == -1) break;

			S.replace(res, 7, "Hoshina");
		}
		cout << S << "\n";
	}
	return 0;
}

Measured memory_bytes: 3180
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#define M_PI       3.14159265358979323846


using namespace std;

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FILL(a, x) memset(a, x, sizeof(a))

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)


int main() {
	int w, h, x, y;
	cin >> w >> h >> x >> y;
	int b = 0;
	if (x * 2 == w && y * 2 == h) b = 1;
	printf("%.12f %d\n", (double)w*(double)h*0.5, b);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;
typedef long double ld;
int main(){
    ll n; cin>>n; 
    if(n>=30){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
s.find_by_order(x) xth element in set
x.order_of_key(x) number of elements <x*/
#define ll long long
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define extract_word(s)  stringstream str(s); while(str>>word)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SET(s) cout<<fixed<<setprecision(s)
#define chotu 1000000007
#define set0(a) memset(a,0,sizeof(a))
#define endl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define lower_string(s) transform(all(s),s.begin(),::tolower())
#define upper_string(s) transform(all(s),s.begin(),::toupper())
#define size(s) s.size()
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<typename T,typename U>
bool compare(T x,U y){return(abs(x-y)<=1e-9);}
void solve()
{
fastio
string s;
cin>>s;
string ans;
for(auto &x:s)
{
	if(x=='0')
	ans.pb('0');
	else if(x=='1')
	ans.pb('1');
	else
	{
		if(!ans.empty())
		ans.pop_back();
	}
}
cout<<ans;
}
int main()
{
//code
fastio
int t;
t=1;
while(t--)
{
solve();
cout<<endl;
}
}


Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <utility>
#define maxn 200005
using namespace std;
typedef long long ll;
inline int getint(){
  char c; int res = 0, sig = 1;
  for(c = getchar();c < '0' || c > '9';c = getchar()) if(c == '-') sig = -1;
  for(;c >= '0' && c <= '9';c = getchar()) res = res * 10 + (c - '0');
  return res * sig;
}
int n,q;
char t[maxn],d[maxn];
string s;
bool check_left(int x){
  for(int i = 1;i <= q;i++){
    if(t[i] == s[x - 1]){
      if(d[i] == 'L') x--;
      else x++;
    }
    if(x == 0) return true;
    if(x == n + 1) return false;
  }
  return false;
}
bool check_right(int x){
  for(int i = 1;i <= q;i++){
    if(t[i] == s[x - 1]){
      if(d[i] == 'L') x--;
      else x++;
    }
    if(x == 0) return false;
    if(x == n + 1) return true;
  }
  return false;
}
int main(){
  ios::sync_with_stdio(false);
  cin >> n >> q;
  cin >> s;
  for(int i = 1;i <= q;i++) cin >> t[i] >> d[i];
  int lb = 0, rb = n, ans = n;
  while(lb < rb){
    int mid = (lb + rb + 1) >> 1;
    if(check_left(mid)) lb = mid;
    else rb = mid - 1;
  }
  ans -= lb;
  lb = lb + 1,rb = n + 1;
  while(lb < rb){
    int mid = (lb + rb) >> 1;
    if(check_right(mid)) rb = mid;
    else lb = mid + 1;
  }
  ans -= n - lb + 1;
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 976
def solve():
    N, M = map(int, input().split())
    l = 0
    r = 10 ** 9
    for _ in range(M):
        a, b = list(map(int, input().split()))
        l = max(l, a)
        r = min(r, b)
    
    if l<=r:
        return r-l+1
    else:
        return 0
        
print(solve())

Measured memory_bytes: 3188
import java.util.*;

public class Main{
	
	private static final Scanner scan = new Scanner(System.in)
							.useDelimiter("[,\\s]+");
	static boolean dirs[] = new boolean[4];

	public static void main(String[] args){
		
		while(scan.hasNext()){
			double[] x = new double[4];
			double[] y = new double[4];
			for(int i = 0; i < 4; i++){
				x[i] = scan.nextDouble();
				y[i] = scan.nextDouble();
			}
			System.out.println(solve(x,y));
		}
	}

	static String solve(double[] x, double[] y){
		for(int i = 0; i < 4; i++){
			int j = (i+1) % 4;
			int k = (i+2) % 4;
			dirs[i] = cross(x[j]-x[i], y[j]-y[i], x[k]-x[i], y[k]-y[i]);
		}
		boolean yes = true;
		for(int i = 1; i < 4; i++){
			if(dirs[i-1] != dirs[i]){
				yes = false;
			}
		}
		return yes? "YES" : "NO";
	}

	private static boolean cross(double x1, double y1, double x2, double y2){
		return (x1*y2 - x2*y1) >= 0;
	}
}

Measured memory_bytes: 28348
#include "bits/stdc++.h"

using namespace std;

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

    double r0,w0,c,r;
    while(cin>>r0>>w0>>c>>r,r0||w0||c||r){
        if(r0/w0>=c) cout<<0<<endl;
        else cout<<(int)ceil((c*w0-r0)/r)<<endl;
    }
}

Measured memory_bytes: 3216
# -*- coding: utf-8 -*-

def count(val1, val2):
    digit = 1
    while val1 >= (val2 ** digit):
        digit += 1

    res = 0
    while digit!=0:
        cnt = int(val1 // val2 ** digit)
        val1 -= (val2 ** digit)*cnt
        res += cnt
        digit -= 1

    return res,val1


N = int(input())
ans = N

for i in range(0,N+1):
    n = i
    m = N - i
    res = 0

    cnt, nn = count(n, 9)
    n = nn
    res += cnt

    cnt, mm = count(m, 6)
    m = mm
    res += cnt

    res += n + m
    ans = min(ans, res)

print(ans)


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amin(T& a,T b){ a=min(a,b);}

array<bool, 5050> dp;

bool ck(int s, int k, const VI& v){
	int n=sz(v);
	if(v[s] >=k) return true;
	dp.fill(false); dp[0]=true;
	rep(j, n) if(s!=j ) {
		repr(u, k, 0) if(dp[u] && u+v[j] <=k){
			dp[u+v[j]] = true;
			if(u+v[j]>=k-v[s] && u+v[j]<k){
				//dbg(s,dp[s],"true");
				return true;
			}
		}
	}
	return false;
}




int main(){
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n,k;
	cin >>n >>k;
	VI a(n);
	for(auto& z: a) cin >>z;
	a.push_back(k); n++;
	sort(all(a));

	//int ans =0;
	//for(auto x :a) cerr<<x<<" "; puts("");
	//rep(i, sz(a)){
	//	if(!ck(i, k, a)) ans++;;
	//}
	//dbg(ans);
	int lo=0-1, hi=n-1;
	while(hi - lo >1){
		int md = (hi + lo) >> 1;
		if( ck(md, k, a) ) hi = md; else lo = md; 
	}
	cout << hi <<"\n";
	return 0;
}

Measured memory_bytes: 256
import java.io.*; 
import java.math.*;
import java.util.*;
import java.awt.Point;
 
public class Main {
	static final long MOD = 998244353L;
	//static final long INF = -1000000000000000007L;
	//static final long MOD = 1000000007L;
	//static final int INF = 1000000007;
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		if (sc.ni()+sc.ni()+sc.ni()>21) {
			pw.println("bust");
		} else {
			pw.println("win");
		}
		pw.close();
 	}
	
	//Fast exponentiation (x^y mod p)
	public static long power(long x, long y, long p) { 
		// Initialize result
		long res = 1;

		// Update x if it is more   
		// than or equal to p 
		x = x % p;  

		while (y > 0) { 
			// If y is odd, multiply x 
			// with result 
			if((y & 1)==1) 
				res = (res * x) % p; 

			// y must be even now 
			// y = y / 2 
			y = y >> 1;  
			x = (x * x) % p;  
		} 
		return res; 
	}
	
    public static int[][] sort(int[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    int[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<int[]>() {
			  @Override
        	  public int compare(int[] arr1, int[] arr2) {
				  return arr1[2]-arr2[2]; //ascending order
	          }
		});
		return array;
	}
    
    public static long[][] sort(long[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    long[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<long[]>() {
			  @Override
			  //Descending order
        	  public int compare(long[] arr1, long[] arr2) {
				  if (arr2[0] < arr1[0])
					  return -1;
				  if (arr2[0] > arr1[0])
					  return 1;
				  return 0;
	          }
		});
		return array;
	}
    
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int ni() { 
            return Integer.parseInt(next()); 
        } 
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str;
        }
    }
}

Measured memory_bytes: 21332
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

void dfs(const int i, const int& n, const vector<int>& a, bool f, int& ans) {
    if (i>=n) {
        if (f) ans++;
        return;
    }

    for (int j=-1; j<=1; j++) {
        const int bi = a[i] + j;
        dfs(i+1, n, a, f || (bi%2==0), ans);
    }
}

int main() {
    int n;
    cin >> n;
    int ans = 0;
    vector a(n,0);
    for (int i=0; i<n; i++) cin >> a[i];
    dfs(0, n, a, false, ans);
    cout << ans << endl;
}

Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

// struct SegmentTree {
//     int n;
//     vector<int> node;

//     SegmentTree(vector<int> v) {
//         int sz = v.size();
//         n = 1; while(n < sz) n *= 2;
//         node.resize(2*n-1, INF);

//         for(int i=0; i<sz; i++) node[i+n-1] = v[i];
//         for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]);
//     }

//     // 値の更新
//     void update(int x, int val) {
//         x += (n - 1);

//         node[x] = val;
//         while(x > 0) {
//             x = (x - 1) / 2;
//             node[x] = min(node[2*x+1], node[2*x+2]);
//         }
//     }

//     // [a, b) の最小値を求める
//     int getmin(int a, int b, int k=0, int l=0, int r=-1) {
//         if(r < 0) r = n;

//         if(r <= a || b <= l) return INF;
//         if(a <= l && r <= b) return node[k];

//         int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
//         int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
//         return min(vl, vr);
//     }
// };

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

    int N;
    cin >> N;
    vector<int> A(N);
    map<int, int> idx;
    REP(i, N) cin >> A[i];
    REP(i, N) idx[A[i]] = i;

    llint ans = 0;
    set<int> st;    // 自分より小さいやつのindexが入ったset
    st.emplace(-1);
    st.emplace(N);

    FOR(i, 1, N+1){
        auto itr = st.lower_bound(idx[i]);
        int right = (*itr) - idx[i];
        itr--;
        int left = idx[i] - (*itr);
        ans += (llint)A[idx[i]]*left*right;
        st.emplace(idx[i]);
    }

    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 19840
import sys, math
from functools import lru_cache
import numpy as np
import heapq
from collections import defaultdict
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def lcm(a, b):
    return a*b//math.gcd(a, b)


def main():
    N, K = mi()
    print(N-K+1)

if __name__ == '__main__':
    main()


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

int main(){
    string s;
    cin >> s;
    if(s == "AAA" || s == "BBB") cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3560
n,p = gets.split(" ").map { |v|
	v.to_i
}

arr = gets.split(" ").map { |v|
	v.to_i
}


e = [1]
o = [0]

for i in 1..n do
	if arr[i-1] % 2 == 0 then
		e << (e[i-1]) * 2
		o << (o[i-1]) * 2
	else
		e << (e[i-1]) + o[i-1]
		o << (o[i-1]) + e[i-1]
	end	
end

if p == 0 then
puts e[-1]
else
	puts o[-1]
end


Measured memory_bytes: 1788
import collections

N,K = input().split()
A = list(map(int, input().split()))

N = int(N)
K = int(K)
P = []

for k ,v in collections.Counter(A).items():
    P.append(v)

P.sort()

Del = len(P) - K
t = 0

if Del < 1:
    Del = 0
else:
    for i in range(Del):
        t += int(P[i])

print(t)

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

using namespace std;

int main(void)
{
  int a,b,c,k;
  int tmp=0;

  cin>>a>>b>>c>>k;

  if(a>=k)
  {
    cout<<k<<endl;
    return 0;
  }
  else if((a+b) >= k)
  {
    cout<<a<<endl;
    return 0;
  }
  else if((a+b+c) >= k)
  {
    cout<<a - (k-(a+b)) <<endl;
    return 0;
  }
}

Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    int a[n], b[n], c[n-1];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n - 1; i++) {
        cin >> c[i];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += b[a[i]];
        if (i > 0 && a[i] == a[i-1] + 1) {
            ans += c[a[i-1]];
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import java.io.*;  
 public class Main {
    public static void main(String[] args) 
{
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        try 
     {
            String[] str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            if(a < b)
           {
            System.out.println("a < b");
            }
           else if(a > b)
           {
            System.out.println("a > b");
            }
           else
            {
            System.out.println("a == b");
            }
        } catch(IOException e) {
            e.printStackTrace();
        }
     }
}

Measured memory_bytes: 24284
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	defer writer.Flush()

	S, T := ReadString(), ReadString()
	s := make([]int, len(S)+1)
	for i := 0; i < len(S); i++ {
		v := 1
		if S[i] == 'B' {
			v = 2
		}
		s[i+1] = s[i] + v
		s[i+1] %= 3
	}
	t := make([]int, len(T)+1)
	for i := 0; i < len(T); i++ {
		v := 1
		if T[i] == 'B' {
			v = 2
		}
		t[i+1] = t[i] + v
		t[i+1] %= 3
	}

	q := ReadInt()
	for i := 0; i < q; i++ {
		a, b, c, d := ReadInt(), ReadInt(), ReadInt(), ReadInt()
		if (s[b]+3-s[a-1])%3 == (t[d]+3-t[c-1])%3 {
			Println("YES")
		} else {
			Println("NO")
		}
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}

var writer = bufio.NewWriter(os.Stdout)

func Printf(format string, a ...interface{}) { fmt.Fprintf(writer, format, a...) }
func Println(a ...interface{})               { fmt.Fprintln(writer, a...) }


Measured memory_bytes: 6408
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <set>
#include <string>
#include <utility>
#include <vector>

int main()
{
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    long long ans = 0ll;
    for (auto& e : a) {
        std::cin >> e;
    }
    std::sort(a.begin(), a.end(), std::greater<long long>());
    for (int i = 0; i < (n - 1); i++) {
        ans += a.at(i / 2 + i % 2);
    }
    std::cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 4496
# 解説
import sys
pin = sys.stdin.readline
pout = sys.stdout.write
perr = sys.stderr.write

N, M, K = map(int, pin().split())
A = list(map(int, pin().split()))
B = list(map(int, pin().split()))
a = [0]
b = [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
ans = 0

for i in range(N + 1):
    #Aの合計がKを超えるまで比較する
    if a[i] > K:
        break
    # 超えていた場合に本の個数を減らす
    while b[M] > K - a[i]:
        M -= 1
    ans = max(ans, M + i)
print(ans)


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

using namespace std;

#define int long long 

int32_t main()
{
	//ios_base::sync_with_stdio(false);cin.tie(0);
	int n,q,sum = 0,a,b;
	map<int,int>m;
	cin >> n;
	for(int i = 1; i <= n;i++)
	{
		cin >> a;
		m[a]++;
		sum+=a;
	}
	cin >> q;
	for(int i = 1; i <= q; i++)
	{
		cin >> a >> b;
		int diff = b - a;
		int times = m[a];
		sum += (diff*times);
		cout << sum << endl;
		m[b]+=m[a];
		m[a] = 0;
	}
	return 0;
}


Measured memory_bytes: 9240
#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 SIZE(x) ((int)(x).size())
#define MIN(c) (*min_element(ALL(c))) 
#define MAX(c) (*max_element(ALL(c)))
#define ACC(c) (accumulate(ALL(c), 0))
#define SLL(x, n) ((x) << (n))
#define SRL(x, n) ((x) >> (n))
#define MP(a, b) (make_pair((a), (b)))
#define ENDL "\n"
#define PRINT(x) cout << (x) << ENDL

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

inline int in(int& a) {return scanf("%d", &a);}
inline void out(int n) {printf("%d\n", n);}
template<typename T> inline void swap(T& a, T& b) {T tmp = a; a = b; b = tmp;}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};

const int MOD = (int)(1e9 + 7);
int N, M;
int a[100000];
ll dp[100001];

ll solve(){
    REP(i, N + 1) dp[i] = 0;
    dp[0] = 1;
    REP(i, M) dp[a[i]] = -1;
    FOR(i, 0, N){
        if(dp[i] == -1) continue;
        if(dp[i + 1] != -1) dp[i + 1] = (dp[i + 1] + dp[i] % MOD) % MOD;
        if(i + 2 <= N && dp[i + 2] != -1) dp[i + 2] = (dp[i + 2] + dp[i] % MOD) % MOD;
    }
    if(dp[N] == -1) return 0;
    else return dp[N];
}

signed main(){
    in(N); in(M);
    REP(i, M) in(a[i]);
    PRINT(solve());
    return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i>0;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
int n;
int a[1010101];
int main()
{
//	freopen("A.in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	ll pr=-1,l=0,ans=0;
	For(i,n) {
		ll t;cin>>t;
		if(t==pr) ++l;
		else pr=t,ans+=l/2,l=1;
	}
	cout<<ans+l/2;
	return 0;
}


Measured memory_bytes: 256
/**
 * The man who codes no bugs
 * McCheng is the man studying Maths in CUHK with IQ200
 * @author McCheng
 */

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

class DSumOfDivisors {
public:
    static constexpr int kStressCount = 0;
    static void generateTest(ostream& test) {}
	void solve(istream& cin, ostream& cout) {
        int n;
        cin>>n;
        vector<int> v(n+1, 1);
        for (int i = 2; i < n + 1; i++) {
            for (int j = i; j < n+1; j+=i) {
                v[j]++;
            }
        }
        long long ans=0;
        for (int i = 1; i <= n; i++) {
            ans+=1LL*i*v[i];
        }
        cout<<ans;
	}
};

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream &in(cin);
    ostream &out(cout);
    out << fixed;
    out.precision(20);
    DSumOfDivisors solver;
    solver.solve(in, out);
}


Measured memory_bytes: 42260
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

#define bit(x) (1<<(x))
const int N=(1<<19)+10;
int n,m,k,a,b,c;
int mask[30],cmask[30],nxt0[N][25];
ll dp[N];

bool valid(int x,int S) { return (S&mask[x])==cmask[x];}
void gao() {
	per(i,0,n-1) per(S,0,bit(n-1)) if (S&bit(i)) dp[S]+=dp[nxt0[S][i]];
	rep(S,0,bit(n-1)) dp[S]%=mod;
}
int main() {
	scanf("%d%d%d",&n,&m,&k);
	rep(i,0,k) {
		scanf("%d%d%d",&a,&b,&c); --a; --b;
		mask[a]|=(1<<b);
		cmask[a]|=(c<<b);
	}
	rep(S,0,bit(n-1)) {
		int nxt=n-1;
		per(i,0,n-1) if (S&bit(i)) {
			if (nxt!=n-1) nxt0[S][i]=S^bit(i)^bit(nxt);
			else nxt0[S][i]=S^bit(i);
		} else nxt=i;
	}
	rep(S,0,bit(n-1)) if (valid(0,S)) dp[S]=1;
	rep(i,1,m) {
		gao();
		rep(S,0,bit(n-1)) if (!valid(i,S)) dp[S]=0;
	}
	ll ret=0;
	rep(S,0,bit(n-1)) ret+=dp[S];
	printf("%lld\n",ret%mod);
}


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

int main(int argc, char *argv[])
{
	int r, g, b, sum;
	cin >> r >> g >> b;

	sum = r * 100 + g * 10 + b;
	if (sum % 4 == 0)
		cout << "YES";
	else
		cout << "NO";

	cout << endl;
	
	return 0;
}


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


number=1
B=[]
for i in range(N):
    if A[i]==number:
        number+=1
        B.append(A[i])

#print(B,number)

if len(B)==0:
    print(-1)
else:
    print(N-len(B))


Measured memory_bytes: 24744
/*  -*- coding: utf-8 -*-
 *
 * b.cc: D: 3N Numbers
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int MAX_N3 = MAX_N * 3;

typedef long long ll;
const ll LINF = 1LL << 60;

/* typedef */

typedef multiset<int> msi;
typedef multiset<int,greater<int> > msig;

/* global variables */

int as[MAX_N3];
ll bs[MAX_N3 + 1], cs[MAX_N3 + 1];
msi bset;
msig cset;

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);
  int n2 = n * 2, n3 = n * 3;

  for (int i = 0; i < n3; i++) scanf("%d", &as[i]);

  for (int i = 0; i < n3; i++) {
    bs[i + 1] = bs[i] + as[i];
    bset.insert(as[i]);
    if (bset.size() > n) {
      msi::iterator mit = bset.begin();
      bs[i + 1] -= *mit;
      bset.erase(mit);
    }
  }
  
  for (int i = n3 - 1; i >= 0; i--) {
    cs[i] = cs[i + 1] + as[i];
    cset.insert(as[i]);
    if (cset.size() > n) {
      msi::iterator mit = cset.begin();
      cs[i] -= *mit;
      cset.erase(mit);
    }
  }
  
  ll maxsc = -LINF;
  for (int i = n; i <= n2; i++) {
    ll sc = bs[i] - cs[i];
    if (maxsc < sc) maxsc = sc;
  }

  printf("%lld\n", maxsc);
  return 0;
}


Measured memory_bytes: 15488
n = int(input())
a = [int(i) for i in input().split()]

a.sort(reverse=True)
a.append(0)

#after win=false first win = true
ans = False

for i in range(n):
    if i+1>=a[i+1]:
        ans=(((a[i]-i)%2)==0)
        for j in range(i+1,n+1):
            if a[j]<=i:
                ans = ans or (((i-j)%2)==0)
                break
        break

if ans:
    print("First")
else:
    print("Second")

Measured memory_bytes: 14212
import java.util.*;
import java.io.*;
public class Main
{   
    static int arr[]=new int[100008];
    static int dp[]=new int[100008];
    public static int getAns(int arr[],int index,int n,int k)
      {
          if(index>=n)return 0;
          if(dp[index]!=-1)return dp[index];
          int ans=Integer.MAX_VALUE;
          for(int i=1;i<=k;i++)
           if((index+i)<=n)
            ans=Math.min(ans,Math.abs(arr[index+i]-arr[index])+getAns(arr,index+i,n,k));
          return dp[index]=ans;
      }
	public static void main(String[] args)throws IOException {
		FastReader kb=new FastReader();
        int n=kb.nextInt();
        int k=kb.nextInt();
        Arrays.fill(dp,-1);
        for(int i=1;i<=n;i++)
	     {
	         arr[i]=kb.nextInt();
	     }
	    System.out.println(getAns(arr,1,n,k));
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
  
}













Measured memory_bytes: 50040
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

template <typename T>
class SegmentTree{
private:
    int n;
    vector<T> dat;
public:
    void init(int n_){
        n = 1;
        while(n < n_) n *= 2;
        dat.assign(2*n-1, -1);
    }
    // k: index(0-indexed), a: value
    void update(int k, T a){
        k += n-1;
        dat[k] = a;
        while(k>0){
            k = (k-1)/2;
            dat[k] = max(dat[k*2+1], dat[k*2+2]);
        }
    }
    // query(a, b) =>  minimum in [a,b]
    T query(int a, int b){
        return _query(a, b, 0, 0, n-1);
    }
    // dat[k] is minimum in [l,r]
    T _query(int a, int b, int k, int l, int r){
        if(r<a || b<l) return -1;
        if(a<=l&&r<=b){
            return dat[k];
        }else{
            T vl = _query(a, b, k*2+1, l, (l+r)/2);
            T vr = _query(a, b, k*2+2, (l+r)/2+1, r);
            return max(vl, vr);
        }
    }
};

ll x[100002];
ll v[100002];
ll N, C;

ll solve(){
    ll ret = 0;
    SegmentTree<ll> seg;
    seg.init(N + 1);
    seg.update(0, 0);

    ll v_sum = 0;
    for(int i=0;i<N;i++){
        v_sum += v[i];
        ret = max(ret, v_sum - x[i]);
        seg.update(i + 1, v_sum - x[i]);
    }

    v_sum = 0;
    for(int i=N-1;i>=1;i--){
        v_sum += v[i];
        ret = max(ret, v_sum - 2 * (C - x[i]) + seg.query(0, i));
    }

    return ret;
}

int main(){
    cin >> N >> C;

    for(int i=0;i<N;i++){
        cin >> x[i] >> v[i];
    }

    ll ans = solve();
    for(int i=0;i<N;i++){
        x[i] = C - x[i];
    }
    for(int i=0;i<N/2;i++){
        swap(x[i], x[N - 1 - i]);
        swap(v[i], v[N - 1 - i]);
    }
    ans = max(ans, solve());
    cout << ans << endl;

    return 0;
}

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

string s;

int main(){
    cin >> s;
    int ans = 0;
    if(s.size() % 2 == 1 ){
        rep(i,(s.size()-1)/2){
            if(s[i] == s[s.size()-i-1]) continue;
            else{
                ans++;
            }
        }
    }
    else{
        rep(i,s.size()/2){
            if(s[i] == s[s.size()-1-i]) continue;
            else{
                ans++;
            }
        }
    }

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

Measured memory_bytes: 256