akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os, const map<T,U>& mp){ os << "{"; for(auto& p : mp){ os << p << ","; } os << "}"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int,int>;
using vi = std::vector<int>;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

ll dp[100005][2];

int main(){
    string L; cin >> L;
    int n = L.size();

    dp[0][0] = 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            for(int a=0;a<2;a++){
                for(int b=0;b<2;b++){
                    if(a && b) continue;
                    if(!j){
                        if(a + b > L[i]-'0') continue;
                        dp[i+1][j || a+b < L[i]-'0'] += dp[i][j];
                        dp[i+1][j || a+b < L[i]-'0'] %= mod;
                    }else{ // 未満確定
                        dp[i+1][j] += dp[i][j];
                        dp[i+1][j] %= mod;
                    }
                }
            }
        }
    }

    /* for(int i=0;i<=n;i++){ */
    /*     cout << "i = " << i << endl; */
    /*     for(int j=0;j<2;j++){ */
    /*         cout << dp[i][j] << " "; */
    /*     } */
    /*     cout << endl; */
    /* } */

    cout << (dp[n][0] + dp[n][1])%mod << endl;
}


Measured memory_bytes: 5304
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

int N, A;
vector<int> x;

int main()
{
    cin >> N >> A;
    x.resize(N);
    for (auto &v : x)
    {
        cin >> v;
        v -= A;
    }
    vector<vector<lint> > dp(N+1, vector<lint>(1 + 50*N * 2));
    int shift = 50*N;
    dp[0][shift] = 1;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<=50*N*2; j++)
        {
            dp[i+1][j] = dp[i][j];
            if (j-x[i] >= 0 && j-x[i] <= 50*N*2) dp[i+1][j] += dp[i][j-x[i]];
        }
    }
    cout << dp[N][shift] - 1 << endl;
}


Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MD 1000000007
#define INF 1ll<<60
typedef pair<ll, ll> P;
template <typename T>
std::string tostr(const T &t){std::ostringstream os;os << t;return os.str();}
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

int main(){
    map<string,int> mp;
    int n,cnt=0;
    cin>>n;
    for(int i=0;i<n;i++){
        string tmp;
        cin>>tmp;
        if(mp.count(tmp)) {
            mp[tmp]++;
            cnt=max(cnt,mp[tmp]);
        }
        else {
            mp[tmp]=1;
            cnt=max(cnt,mp[tmp]);
        }
    }
    vector<string> ans;
    for(auto itr=mp.begin();itr!=mp.end();itr++){
        if(itr->second==cnt) ans.push_back(itr->first);
    }
    for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
    return 0;
}


Measured memory_bytes: 26868
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

using VLL = vector <long long>;
using VPILL = vector < pair<long long, int> >;
int N;
VLL X;
VLL Y;
VLL P;
VLL ans;
VLL defaultMinDist;
VPILL PX;
VPILL PY;
int xcho;
int ycho;

const long long INF = 1000000000LL * 1000000000LL;

void solve(int now, int chosen) {
    if (now == N) {
        VLL minDist(defaultMinDist);

        long long res = 0;
        long long lastX = -INF;
        long long lastY = -INF;

        for (int i = 0; i < N; ++i) {
            // x axis
            if (xcho & (1 << PX[i].second)) {
                lastX = PX[i].first;
            }

            minDist[PX[i].second] = min(minDist[PX[i].second], PX[i].first-lastX);

            // y axis
            if (ycho & (1 << PY[i].second)) {
                lastY = PY[i].first;
            }

            minDist[PY[i].second] = min(minDist[PY[i].second], PY[i].first-lastY);
        }

        // backward
        lastX = INF;
        lastY = INF;

        for (int i = N-1; i >= 0; --i) {
            // x axis
            if (xcho & (1 << PX[i].second)) {
                lastX = PX[i].first;
            }

            minDist[PX[i].second] = min(minDist[PX[i].second], lastX-PX[i].first);

            // y axis
            if (ycho & (1 << PY[i].second)) {
                lastY = PY[i].first;
            }

            minDist[PY[i].second] = min(minDist[PY[i].second], lastY - PY[i].first);
        }

        for (int i = 0; i < N; ++i) {
            res += P[i] * minDist[i];
        }

        ans[chosen] = min(ans[chosen], res);
        return ;
    }

    solve(now+1, chosen);

    xcho |= (1<<now);
    solve(now+1, chosen+1);
    xcho &= ~(1<<now);

    ycho |= (1<<now);
    solve(now+1, chosen+1);
    ycho &= ~(1<<now);
}

int main() {
    cin >> N;

    X = VLL(N);
    Y = VLL(N);
    P = VLL(N);
    defaultMinDist = VLL(N, INF);

    PX = VPILL(N);
    PY = VPILL(N);

    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> Y[i] >> P[i];
        PX[i] = make_pair(X[i], i);
        PY[i] = make_pair(Y[i], i);
        defaultMinDist[i] = min(defaultMinDist[i], min(abs(X[i]), abs(Y[i])));
    }

    ans = VLL(N+1, INF);
    xcho = 0;
    ycho = 0;

    sort(PX.begin(), PX.end());
    sort(PY.begin(), PY.end());
    solve(0, 0);

    for (int k = 0; k <= N; ++k) {
        cout << ans[k] << endl;
    }

    return 0;
}

Measured memory_bytes: 3616
def resolve():
    A, B, C, X, Y = map(int, input().split())
    C *= 2
    AB = A+B
    ans = 0
    while X > 0 or Y > 0:
        min_cnt = min(X, Y)
        if X and Y:
            if min_cnt*C <= (A*min_cnt) + (B*min_cnt):
                ans += min_cnt*C
                X -= min_cnt
                Y -= min_cnt
            else:
                ans += (A*min_cnt) + (B*min_cnt)
                X -= min_cnt
                Y -= min_cnt
        else:
            if max(X, Y)*C <= (A*X) + (B*Y):
                ans += max(X, Y)*C
                X -= max(X, 0)
                Y -= max(Y, 0)
            else:
                ans += (A*X) + (B*Y)
                X -= max(X, 0)
                Y -= max(Y, 0)
    return print(ans)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var s = Console.ReadLine();
        var t = Console.ReadLine();

        var ans = 0;
        for (int i = 0; i < 3; i++)
        {
            if (s[i] == t[i]) ans++;
        }

        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 13140
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    count = 0
    for i, a in enumerate(As):
        if (i+1) % 2 == 0:
            continue
        if a % 2 == 0:
            continue

        count += 1

    return count


def main():
    print(solve())


if __name__ == "__main__":
    main()


Measured memory_bytes: 9040
n, k = map(int, input().split())

xys = {}
xs = []
ys = []
for i in range(n):
  x, y = map(int, input().split())
  xys[i] = (x, y)
  xs.append(x)
  ys.append(y)
xs = sorted(xs)
ys = sorted(ys)
min_area = float('inf')

for li in range(n):
  for ri in range(li+1, n):
    left = xs[li]
    right = xs[ri]
    for bi in range(n):
      for ti in range(bi+1, n):
        bottom = ys[bi]
        top = ys[ti]
        area = (top - bottom) * (right - left)
        cnt = 0
        for i in range(n):
          xi, yi = xys[i]
          if (left <= xi <= right) and (bottom <= yi <= top):
            cnt += 1
            if cnt >= k:
              break
        if cnt >= k:
          min_area = min([min_area, area])

print(min_area)


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

N,M = list(map(int, input().rstrip().split()))
pS_list = []

for i in range(M):
    inp = input().rstrip().split()
    pS_list.append( [int(inp[0]), inp[1]] )

#-----
problem_AC_set = set()
problem_WA_dic = {}

for p,S in pS_list:
    if (S == "AC") and (p not in problem_AC_set):
        problem_AC_set.add(p)
    
    if (S == "WA") and (p not in problem_AC_set):
        problem_WA_dic.setdefault(p, 0)
        problem_WA_dic[p] += 1

cnt_AC = len(problem_AC_set)
cnt_WA = sum([v for k,v in problem_WA_dic.items() if k in problem_AC_set])

print(cnt_AC, cnt_WA)


Measured memory_bytes: 28168
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  string s1;
  cin>>n>>s1>>k;
  for(int i=0;i<s1.size();i++)
    if(s1[i]!=s1[k-1])cout<<"*";
    else cout<<s1[i];
  cout<<"\n";
  return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){ int a,b,c,d;
    cin >> a >> b >> c >> d;
    
    while(1){
        c-=b;
        if(c<=0){ cout << "Yes"<<endl; break;}
        a-=d;
        if(a<=0){ cout << "No" << endl; break;}
    }

    return 0;
}

Measured memory_bytes: 3636
#include<cstdio>
const int N = 110000 + 10;
using namespace std;
int f[N], n, ans;
inline int ckmx(int a,int b) {return a > b ? a : b;}
int fk(int x) {return x + 2;}
int main()
{
  scanf("%d",&n);
  int x=0;
  for(int i=1; i<=n; ++i) 
  {
  	scanf("%d",&x);
    f[fk(x-1)] ++; ans=ckmx(ans,f[fk(x-1)]);
    f[fk(x)] ++; ans=ckmx(ans,f[fk(x)]);
    f[fk(x+1)] ++; ans=ckmx(ans,f[fk(x+1)]);
  }
  printf("%d\n",ans);
}

Measured memory_bytes: 512
using System;
using System.Linq;
using System.Threading.Tasks;

static class Program
{
  static void Main()
  {
    var inputVal = Console.ReadLine().Split(' ');
    int A = int.Parse(inputVal[0]);
    int P = int.Parse(inputVal[1]);
    int val = 0;
    val = A * 3 + P;
    val /= 2;
    Console.WriteLine(val);
  }
}

Measured memory_bytes: 13140
import Data.List(intercalate)

main :: IO ()
main = readLn >>= putStrLn . intercalate ":" . map show . secsToHMS

secsToHMS :: Int -> [Int]
secsToHMS secs0 =
    let (h, secs1) = secs0 `divMod` 3600
        (m, s) = secs1 `divMod` 60
    in [h, m, s]

Measured memory_bytes: 3688
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int k = sc.nextInt();
		
		for(int i=1;i<=k;i++) {
			if(a>=b) {
				b*=2;
			}
			else {
				c*=2;
			}
		}
		if(c>b && b>a) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 35840
/*
  Contest 109
  B - Shiritori
  Rakesh Kumar --> 27/09/2020
 */

#include <bits/stdc++.h>

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

    int n = 0;
    std::cin >> n;
    std::cin.ignore();
    std::unordered_map<std::string, bool> dict;
    std::string last;
    std::getline(std::cin, last); --n;
    dict[last] = true;
    std::string r = "Yes";
    while (n--) {
        std::string s;
        std::getline(std::cin, s);
        if (dict.find(s) != dict.end())
            r = "No";
        else
            if (s[0] != last[last.size() - 1])
                r = "No";
        dict[s] = true;
        last = s;
    }
    std::cout << r << std::endl;

    return 0;
}


Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
int f[220000];
int main(){
    int n;cin >> n;
    vi a(n);
    rep(i,n){
        cin >> a[i];
        f[a[i]]=f[a[i]-1]+1;
    }
    int ans=0;
    rep(i,n+1){
        ans=max(ans,f[i]);
    }
    cout << n-ans << endl;
    return 0;
}

Measured memory_bytes: 1792
while True:
    L = []
    n = int(input())
    if n == 0:
        break
    for i in range(n):
        r =  list(input().split())
        t = r.pop(0)
        w = l = 0
        for a in r:
            if int(a) == 0:
                w += 1
            elif int(a) == 1:
                l += 1
        L.append((t,w,l,i))

    for i in sorted(L, key = lambda x:(-x[1],x[2],x[3])):
        print(i[0])


Measured memory_bytes: 5604
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<tuple>
#include<utility>
#include<stack>
#include<set>
#include<iomanip>
using namespace std;
using ll=long long int ;

int main() {

	ll n;
	cin >> n;
	ll ans = 1;

	for (ll i = 1; i <= n; i++) {
		ans = ans*i % 1000000007;
	}

	cout << ans << endl;;

		return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    // Your code here!
    int n;
    vector<ll> ryuka={2,1};
    cin>>n;
    for(int i=2;i<=n;i++){
        ryuka.push_back(ryuka[i-1]+ryuka[i-2]);
    }
    cout<<ryuka[n];
}


Measured memory_bytes: 384
use std::io;
use std::str::FromStr;

fn input<T:FromStr>() -> T {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().parse().ok().unwrap()
}

fn main() {
    let n: String = input();
    let n: Vec<char> = n.chars().collect();
    for i in n {
        if i == '1' {
            print!("9");
        } else {
            print!("1");
        }
    }
}


Measured memory_bytes: 4352
import numpy as np

n, m = map(int, input().split())
A = np.array([list(input()) for _ in range(n)])
B = np.array([list(input()) for _ in range(m)])

for i in range(n-m+1):
    for j in range(n-m+1):
        if (A[i:i+m, j:j+m] == B).all():
            print('Yes')
            exit()
print('No')

Measured memory_bytes: 26664
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')

dp = [INF] * n
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,n):
    for j in range(1,min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[n-1])

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

int main(void){
   int N;
   cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++){
      cin>>a[i];
   }
   map<int,int> result;
   for(int i=0;i<N;i++){
      result[a[i]]++;
   }
   int ans=0;
   for(int i=0;i<N;i++){
      if(result[a[i]]==a[i]) continue;
      else{
         result[a[i]]--;
         ans++;
      }
   }
   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 5120
import sys,itertools
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
l = list(map(int, input().split()))
t = 0

for i in range(N):
    k = l[i]
    t += k

t_2 = t/2
pre = 0
A = 0
for i in range(N):
    A += l[i]
    d = A-t_2
    if d>0:
        if d>abs(pre):
            A -= l[i]
        break
    pre = d
print(abs(t-2*A))

Measured memory_bytes: 82212
#include<iostream>

using namespace std;

const static int MAX=51;

int H,W;

int map[MAX][MAX];
int dp[MAX][MAX];


void solve(){
	
	dp[0][0]=map[0][0];
	
	for(int i=1;i<W;i++){
		dp[0][i]=map[0][i]+dp[0][i-1];
	}
	
	for(int i=1;i<H;i++){
		dp[i][0]=map[i][0]+dp[i-1][0];
	}
	
	for(int i=1;i<H;i++){
		for(int j=1;j<W;j++){
			dp[i][j]=min(dp[i][j-1],dp[i-1][j])+map[i][j];
		}
	}
	
	cout<<dp[H-1][W-1]<<endl;
	
}


int main(){
	cin>>H>>W;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			char ch;
			cin>>ch;
			map[i][j]=ch-'0';
		}
	}
	solve();
	return 0;
}


Measured memory_bytes: 3132
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(a<c)swap(a, c);
  if(a-c<=d){cout <<"Yes" << endl;exit(0);}
  if(a-b<=d && b-c<=d){cout <<"Yes" << endl;exit(0);}
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
// Author: raghav_0901
#include<bits/stdc++.h>
#define int long long int
#define f(i,s,e) for(i=s;i<e;++i)
#define fr(i,s,e) for(i=s;i>=e;i--)
#define ff(i,s,e,f) for(i=s;i<e && f;++i)
#define mem(arr,val) memset(arr, val, sizeof(arr))
#define mems(arr, val, n) memset(arr, val, n)
#define vec vector<int>
#define pr pair<int,int>
#define lim 1000000
#define mod 1000000007
#define Arena ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

signed main()
{
    Arena
    register int i,j,num,t=1;
    //cin>>t;
    while(t--)
    {
        int n,m;cin>>n>>m;
        int ans = (n*(n-1))/2;
        ans+=(m*(m-1))/2;
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1001001001;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
//printf("%.10f\n", N);
/*
ll memo[100000];
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/

int main(){
    double pi = 3.14159265358979;
    /*cout << pi / atan(1.7320508) << endl;*/
    double A,B,X;
    cin >> A >> B >>X;
    dou H = X / A / A;
    if(H  * 2 >= B){
        dou N = 2 * B - 2 * H;
        dou res = atan(N / A);
        printf("%.10f\n",res / pi * 180);
    }
    else{
        dou N = A * B / X * B / 2;
        dou res = atan(N);
        printf("%.10f\n",res / pi * 180);
    }
}

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

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  vector<int> d(N);
  rep(i, N) cin >> d[i];

  std::sort(d.begin(), d.end(), std::greater<int>());

  int count = 0;
  int before = 0;
  rep(i, N) {
    if (before != d[i]) count++;
    before = d[i];
  }

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
 string S,T;
 cin >> S >> T;
 int l = S.length();
 bool flag = true;
 for(int i=0;i<l;i++){
 	if (S[i]!=T[i]){
		flag=false;
        
	} 
   
 }
 if (flag){
 	cout << "Yes" << endl;
 }else {
 	cout << "No" << endl;
}
}

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

int main(){

	string str;
	long long n, q;


	cin>>n>>q;
	cin>>str;

	int count[n];

	for(int i=0; i<str.length(); i++){
		if(str[i] == 'A' && str[i+1] == 'C'){
			if(i == 0){
				count[i] = 0;
				count[i+1] = 1;
			}
			else{
				count[i] = count[i-1];
				count[i+1] = count[i] + 1;
			}
			i++;
		}
		else{
			count[i] = count[i-1];
		}
	}

	while(q--){
		long long l, r;
		cin>>l>>r;

		cout<<count[r-1] - count[l-1]<<"\n";

	}



	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define EPS      (double)1e-9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type> void line(const Type &a){int cnt=0;for(const auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	
	while(1){
		c-=b;
		if(c<=0){
			cout<<"Yes"<<endl;
			return 0;
		}
		
		a-=d;
		if(a<=0){
			cout<<"No"<<endl;
			return 0;
		}
	}
}

Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include <iomanip>
#include <math.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60
const double PI = 3.14159265358979323846;


// mod付きpower
// x^n
ll modpow(ll x, int n) {
	if (n == 0) return 1LL;
	else if (n % 2 == 0) return modpow((x * x) % MOD, n / 2) % MOD;
	else return (modpow((x * x) % MOD, n / 2) * x) % MOD;
}

// a/bを返す
ll divMod(ll a, ll b) {
	ll res = a * modpow(b, MOD - 2);
	return res % MOD;
}

ll A[100009];

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

	ll N, K; cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> A[i];
	sort(A+1, A + N+1);

	ll num = 1;
	ll tot1 = 0;
	for (ll i = K; i <= N; i++) {
		tot1 += A[i] * num;
		tot1 %= MOD;
		num *= i; num %= MOD;
		num = divMod(num, i - K + 1);
	}
	ll tot2 = 0;
	num = 1;
	reverse(A+1, A + N+1);
	for (ll i = K; i <= N; i++) {
		tot2 += A[i] * num;
		tot2 %= MOD;
		num *= i; num %= MOD;
		num = divMod(num, i - K + 1);
	}
	ll ans = (tot1 - tot2 + MOD) % MOD;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
H,W=map(int,input().split())
if W==1 or H==1:
	print(1)
elif H%2==0 and W%2==0:
	print((H//2)*(W))
elif H%2==1 and W%2==0:
	print(H*W-((H//2)*(W//2))-((H//2)+1)*(W//2))
elif H%2==0 and W%2==1:
	print(H*W-((W//2)*(H//2))-((W//2)+1)*(H//2))
else:
	print(H*W-((H//2)*((W//2)+1))-((H//2)+1)*(W//2))

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

using namespace std;
using ll = long long;

void init();
void solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__  "YES"
#define FALSE__ "NO"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a
#define lcoutln(a) cout << a << endl
#define lcerr(a) cerr << a
#define lcerrln(a) cerr << a << endl
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007
#define PI 3.141592653589793238462643383

signed main()
{
	init();
	solve();
}

int N;
vector<ll> A, B;

void init()
{
	cin >> N;
	A.resize(N);
	B.resize(N);
	rep(i, N) cin >> A[i] >> B[i];
}

void solve()
{
	ll sum = 0;
	rrep(i, N) {
		A[i] += sum;
		if (A[i] % B[i] == 0) continue;
		sum += B[i] - A[i] % B[i];
	}
	cout << sum << endl;
}



Measured memory_bytes: 1792
#include <stdio.h>

int main(void){
  int i, j, h, w;

  while(1){
    scanf("%d%d", &h, &w);
    if(h == 0 && w == 0)  break;
    for(i = 0; i < h; i++){
      for(j = 0; j < w; j++){
	if((i+j) % 2 == 0){
	  printf("#");
	}else{
	  printf(".");
	}
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 572
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
vector<int> adj[100001];
int visited[100001];
void dfs(int u)
{
    // cout<<u<<" ";
    visited[u] = 1;
    for(auto i:adj[u])
        if(visited[i]==0)
            dfs(i);
}
int main()
{
    int n,m;
    cin>>n>>m;
    int i,j,u,v;
    int ans[n];
    for(i=0;i<m;i++)
    {
        cin>>u>>v;
        u--;
        v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    memset(visited,0,sizeof(visited));
    dfs(0);
    for(i=0;i<n;i++)
        if(visited[i]==0)
        {
            cout<<"No";
            return 0;
        }
    memset(visited,0,sizeof(visited));
    list<int> q;
    visited[0]=1;
    q.push_back(0);
    while(!q.empty())
    {
        int s = q.front();
        q.pop_front();
        for(auto i:adj[s])
        {
            if(visited[i]==0)
            {
                visited[i]=1;
                q.push_back(i);
                ans[i] = s+1;
            }
        }
    }
    cout<<"Yes\n";
    for(i=1;i<n;i++)
        cout<<ans[i]<<"\n";
}   


Measured memory_bytes: 14188
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long lng;
#define UP(i,a,b) for(int i=(a); i<=(b); ++i)
#define DOWN(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) UP(i,0,n-1)
#define ALL(a) (a).begin(), (a).end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end()) //NOTE: <a> must be sorted in advance

lng power(lng b, lng n) {lng sol=1; while(n>0) {if(n&1) {sol=sol*b;} n>>=1; b*= b;} return sol;} //calculate b^n

const int MOD = 1000000007; //10^9+7


/*********** variables ************/

/**********************************/

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A,B,C;
    cin >> A >> B >> C;

    if(A*B*C==175) cout << "YES" << endl;
    else cout << "NO" << endl;
}


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

int main(){
    int n;
    int count=0;
    cin >> n;
    for(int i=0;i<n;i++){
        long long a;
        cin >> a;
        while(true){
            if(a%2==0){a/=2;count++;}
            else break;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <memory>
typedef long long ll;
using namespace std;
const ll MAX = 1e10;

int main(int argc, char const *argv[]) {
  int i,j,k;
  int n,m,l;
  int a,b,c;
  int q;
  int s,t;
  ll **cost;
  ll **refuel;

  cin >> n;
  cin >> m;
  cin >> l;
  cost = new ll*[n];
  for (i = 0; i < n; i++) {
    cost[i] = new ll[n];
    for (j = 0; j < n; j++) {
      cost[i][j] = MAX;
    }
    cost[i][i] = 0;
  }
  for (i = 0; i < m; i++) {
    cin >> a;
    cin >> b;
    cin >> c;
    cost[a-1][b-1] = c;
    cost[b-1][a-1] = c;
  }
  for (k = 0; k < n; k++) {
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
        if(cost[i][j] > cost[i][k] + cost[k][j]){
          cost[i][j] = cost[i][k] + cost[k][j];
        }
      }
    }
  }
  refuel = new ll*[n];
  for (i = 0; i < n; i++) {
    refuel[i] = new ll[n];
    for (j = 0; j < n; j++) {
      refuel[i][j] = MAX;
    }
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      if (cost[i][j] <= l) {
        refuel[i][j] = 1;
      }
    }
    refuel[i][i] = 0;
  }
  for (k = 0; k < n; k++) {
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
        if(refuel[i][j] > refuel[i][k] + refuel[k][j]){
          refuel[i][j] = refuel[i][k] + refuel[k][j];
        }
      }
    }
  }
  cin >> q;
  for (i = 0; i < q; i++) {
    cin >> s;
    cin >> t;
    if(refuel[s-1][t-1] == MAX){
      cout << -1 << endl;
    }else{
      cout << refuel[s-1][t-1] - 1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    int min_value = 1000000;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        min_value = min(min_value, v[i]);
    }
    stack<int> min_index;
    min_index.push(n);
    for (int i = n - 1; i >= 0; i--) {
        if (v[i] == min_value) {
            min_index.push(i);
        }
    }
    int cur = 0;
    int ans = 0;
    while (true) {
        int idx = min_index.top();
        min_index.pop();
        while (cur < idx) {
            cur += k - 1;
            ans++;
        }
        cur++;
        if (idx >= n) break;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
n,a,b = map(int,input().split())

M = 10**9+7

# 2**n
twon = pow(2,n,M)

# nCr+1 = nCr * (n-r)/(r+1)
# nCr = A(r)とおくと ※nは固定
# A(r+1) = A(r) * (n-r)/(r+1)
# ここでmod M では、フェルマーの小定理より
# 1/(r+1) === (r+1)**(M-2) ※===は合同記号の意味
# よって　A(r+1) = A(r) * (n-r) * (r+1)**(M-2)
L = [0] * (2*(10**5) + 1)
L[0] = 1
for i in range(len(L)-1):
    L[i+1] = ( L[i] * (n-i) * pow(i+1,M-2,M) ) % M
# nCa
nCa = L[a]

# nCb
nCb = L[b]

ans = twon - 1 - nCa - nCb

print(ans % M)

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


using namespace std;


#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()


ll sum(int n);

void go(){
	int n,k;cin>>n>>k;
	priority_queue<int, vector<int>, greater<>> pq;
	for(int i=0;i<n;i++) {
		int x;cin>>x;
		pq.push(x);
	}
	int ans=0;
	while(k--) {
		ans+=pq.top();pq.pop();
	}
	cout << ans;
}
int main(){
   
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   go();

   return 0;
}

ll sum(int n){                
   if(n == 0){
      return n;
   }else{
      return sum(n/10) + n%10;
   }
}


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

const int MAX_N=5e3,MAX_K=5e3;

int N,K,A[MAX_N];

bool dp[MAX_N+1][MAX_K];

bool C(int x){
	fill(dp[0],dp[0]+K,false);
	dp[0][0]=true;
	REP(j,N){
		fill(dp[j+1],dp[j+1]+K,false);
		int a;
		if (x==j){
			a=0;
		}else{
			a=A[j];
		}
		REP(k,K+1){
			dp[j+1][k]|=dp[j][k];
			if (k+a<K){
				dp[j+1][k+a]|=dp[j][k];
			}
		}
	}
	FOR(j,max<ll>(K-A[x],0LL),K){
		if (dp[N][j]){
			return true;
		}
	}
	return false;
}

void solve(){
	ll sum=0;
	REP(i,N){
		sum+=A[i];
	}
	sort(A,A+N);
	int lb=-1,ub=N;
	while(ub-lb>1){
		int mid=(lb+ub)/2;
		if (C(mid)){
			ub=mid;
		}else{
			lb=mid;
		}
	}
	cout<<ub<<endl;
}

int main(){
	cin>>N>>K;
	REP(i,N){
		cin>>A[i];
	}
	solve();
	return 0;
}


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

int main() {
    int n;cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++)cin >> h.at(i);
    int min1 = abs(h.at(1)-h.at(0)), min2 = 0;
    for (int i = 2; i < n; i++)
    {
        int a = min1;
        min1 = min(min1 + abs(h.at(i)-h.at(i-1)), min2 + abs(h.at(i)-h.at(i-2)));
        min2 = a;
    }
    cout << min1 << endl;
    
    return 0;
}

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

using namespace std;

int main()
{
    long long a, b, c, k;
    cin >> a >> b >> c >> k;

    long long ans = 0;

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

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

int main() {
	int a,b;
	cin>>a>>b;
		if (((a%2==0)&&(b%2==0))||((a%2!=0)&&(b%2!=0)))
			cout<<(a+b)/2<<endl;
		else
			cout<<(a+b)/2+1<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<stdlib.h>
#include<stack>
using namespace std;
#define PI 3.14159265358979
typedef  long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#include<set>
int main(void)
{
    ll b=0;
    ll n;
    cin>>n;
    vector<ll> a(n+3);
    rep(i,n)
    {   
        cin>>a[i];
        b = b^a[i];
    }


    rep(i,n)
    {
        cout<<(b^a[i])<<' ';
    }

        cout<<endl;
}


Measured memory_bytes: 4380
fun main(arr: Array<String>) {
    println(decode())
}

fun decode():String {
    val s = readLine()!!.toMutableList()
    val t = readLine()!!
    for(i in s.size - t.length downTo 0) {
        var isMatch = true
        for(j in t.indices) {
            if(s[j+i] == '?') {
                continue
            }
            if(t[j] != s[j+i]) {
                isMatch = false
                break
            }
        }
        if(isMatch) {
            for(j in t.indices) {
                s[i+j] = t[j]
            }
            return s.map { if(it == '?') 'a' else it }.joinToString("")
        }
    }
    return "UNRESTORABLE"
}


Measured memory_bytes: 36320
import collections
import sys


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


input = sys.stdin.readline
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for i in range(M)]
ans = 0
t = unionFind(N)

for x, y in xy:
    t.unite(x, y)

for i in range(N):
    if t.same(i+1, p[i]):
        ans += 1
print(ans)


Measured memory_bytes: 24796
s=input()
t=input()

ans=10*100

for i in range(len(s)):
  ss=len(t)+i
  a=s[i:ss]
  if len(t) != len(a):
    continue
  aaa=0
  for j in range(len(t)):
    if t[j] != a[j]:
      aaa+=1
  ans=min(ans,aaa)
print(ans)

Measured memory_bytes: 73544
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <functional>
#include <queue>
using namespace std;
typedef long long ll;

const int MAX_V = 370;
using Capacity = int;
using Cost = long long;
const auto inf = numeric_limits<Capacity>::max() / 8;

struct Edge {
	int dst;
	Capacity cap, cap_orig;
	Cost cost;
	int revEdge; bool isRev;
	Edge(int dst, Capacity cap, Cost cost, int revEdge, bool isRev)
		:dst(dst), cap(cap), cap_orig(cap), cost(cost), revEdge(revEdge), isRev(isRev) {
	}
};

struct PrimalDual {
	int n;
	vector<vector<Edge> > g;
	PrimalDual(int n_) : n(n_), g(vector<vector<Edge> >(n_)) {}
	void add_edge(int src, int dst, Capacity cap, Cost cost) { // ?????????
		g[src].emplace_back(dst, cap, cost, g[dst].size(), false);
		g[dst].emplace_back(src, 0, -cost, g[src].size() - 1, true);
	}
	Cost solve(int s, int t, int f) {
		Cost res = 0;
		static Cost h[MAX_V], dist[MAX_V];
		static int prevv[MAX_V], preve[MAX_V];
		for(int i = 0; i < n; i++) {
			h[i] = 0;
		}
		while(f > 0) {
			typedef pair<Cost, int> pcv;
			priority_queue<pcv, vector<pcv>, greater<pcv> > q;
			for(int i = 0; i < n; i++) {
				dist[i] = inf;
			}
			dist[s] = 0;
			q.emplace(pcv(0, s));
			while(q.size()) {
				pcv p = q.top(); q.pop();
				int v = p.second;
				if(dist[v] < p.first) continue;
				for(int i = 0; i < g[v].size(); i++) {
					Edge &e = g[v][i];
					if(e.cap > 0 && dist[e.dst] > dist[v] + e.cost + h[v] - h[e.dst]) {
						dist[e.dst] = dist[v] + e.cost + h[v] - h[e.dst];
						prevv[e.dst] = v;
						preve[e.dst] = i;
						q.emplace(pcv(dist[e.dst], e.dst));
					}
				}
			}
			if(dist[t] == inf) {
				return -1;
			}
			for(int v = 0; v < n; v++) {
				h[v] += dist[v];
			}
			// s-t ????????????????????£??????????????????
			int d = f;
			for(int v = t; v != s; v = prevv[v]) {
				d = min(d, g[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d * h[t];
			for(int v = t; v != s; v = prevv[v]) {
				Edge &e = g[prevv[v]][preve[v]];
				e.cap -= d;
				g[v][e.revEdge].cap += d;
			}
		}
		return res;
	}
	// ??????????????????=???????????????-?????¨??????????????¨???
	void view() {
		for(int i = 0; i < g.size(); i++) {
			for(int j = 0; j < g[i].size(); j++) {
				if(!g[i][j].isRev) {
					Edge& e = g[i][j];
					printf("%3d->%3d (flow:%d)\n", i, e.dst, e.cap_orig - e.cap);
				}
			}
		}
	}
};

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

	int n;
	while(cin >> n, n) {
		PrimalDual pd(370);

		for(int i = 0; i <= 365; i++) {
			pd.add_edge(i, i + 1, 2, 0);
		}
		for(int i = 0; i < n; i++) {
			int x, y, w;
			cin >> x >> y >> w;
			pd.add_edge(x, y + 1, 1, -w);
		}

		cout << -pd.solve(1, 366, 2) << endl;
	}
}

Measured memory_bytes: 3244
#include<iostream>

using namespace std;

int n;
int v[22];
int c[22];
int x;
int y;
int answer;

int main(){
  cin >> n;
  for(int i = 0; i < n; ++i){
    cin >> v[i];
  }
  for(int i = 0; i < n; ++i){
    cin >> c[i];
    if(c[i] < v[i]){
      answer += (v[i] - c[i]);
    }
  }
  cout << answer << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i) < (N); (i)++)
#define all(V) V.begin(), V.end()
using i64 = int_fast64_t;
using P = pair<int,int>;

int main(){
    int A, B;
    cin >> A >> B;
    cout << max(A - 2*B,0) << endl;

}


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

typedef long long int64;
const int inf = (int)1e9;

int main()
{
	while(true) {
		
		int n, m;
		vector<vector<double> > g;
		vector<double> dp[2];
		
		scanf("%d%d", &n, &m);
		if(n == 0)
			break;
		g.resize(n); dp[0].resize(n); dp[1].resize(n);
		for(int i = 0; i < n; ++i) {
			g[i].resize(n);
			for(int j = 0; j < n; ++j)
				scanf("%lf", &g[i][j]);
		}
		
		for(int i = 0; i < n; ++i)
			dp[0][i] = 1;
		
		for(int day = 1; day < m; ++day) {
			
			for(int i = 0; i < n; ++i) {
				
				double &val = dp[day % 2][i];
				val = 0;
				for(int j = 0; j < n; ++j)
					val = max(val, dp[(day - 1) % 2][j] * g[j][i]);
			}
		}
		
		double ans = 0;
		for(int i = 0; i < n; ++i)
			ans = max(ans, dp[(m - 1) % 2][i]);
		
		ans = round(ans * 100) / 100;
		printf("%.2lf\n", ans);
	}
	return 0;
}

/* ハラスメントに負けず */
/* 0完太陽にも負けず */
/* はやく人権を獲得したい */
/* nullmineralが書きましたが */
/* 責任はまったくとりません */

Measured memory_bytes: 1348
///
// File:  0579.go
// Author: ymiyamoto
//
// Created on Mon Mar 19 18:46:50 2018
//
package main

import (
	"fmt"
)

var D, N int

type cloth struct {
	A, B, C int
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	fmt.Scan(&D, &N)
	thermals := make([]int, D+1)

	for i := 1; i <= D; i++ {
		fmt.Scan(&thermals[i])
	}

	clothes := make([]cloth, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&clothes[i].A, &clothes[i].B, &clothes[i].C)
	}

	dp := make([][]int, D+1)
	for i := range dp {
		dp[i] = make([]int, N)
	}

	for i := 1; i < D; i++ {
		for j := 0; j < N; j++ {
			for k := 0; k < N; k++ {
				t1 := thermals[i]
				t2 := thermals[i+1]
				if clothes[j].A <= t2 && t2 <= clothes[j].B && clothes[k].A <= t1 && t1 <= clothes[k].B {
					dp[i+1][j] = max(dp[i+1][j], dp[i][k]+abs(clothes[j].C-clothes[k].C))
				}
			}
		}
	}

	val := 0
	for _, v := range dp[D] {
		val = max(val, v)
	}

	fmt.Println(val)
}



Measured memory_bytes: 1524
#include <iostream>
#include <string>
using namespace std;
using ll = long long;

int main()
{

  string S;
  ll K;
  cin >> S >> K;
  int cnt = 0;
  int firstNum = 0;

  for (int i = 0; i < S.length(); i++)
  {
    int num = S[i] - '0';
    if (num == 1)
    {
      cnt++;
    }
    else
    {
      firstNum = num;
      break;
    }
  }

  if (cnt >= K)
  {
    cout << 1;
  }
  else
  {
    cout << firstNum;
  }

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<time.h>

int main(void)
{
  while(1)
    {
      struct tm car[2]={};
      time_t tim[2];
      int judge=0;
      int i;
      
      for(i=0;i<2;i++)
	{
	  scanf("%d", &car[i].tm_year);
	  if(car[i].tm_year==-1)
	    judge=1;
	  scanf("%d", &car[i].tm_mon);
	  if(car[i].tm_mon==-1)
	    judge=1;
	  scanf("%d", &car[i].tm_mday);
	  if(car[i].tm_mday==-1)
	    judge=1;
	  car[i].tm_year-=1900;
	  car[i].tm_mon-=1;
	  tim[i]=mktime(&car[i]);
	}
      if(judge)break;

      printf("%ld\n",(tim[1]-tim[0])/86400);
    }

  return 0;
}

Measured memory_bytes: 1084
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  while (cin >> N) {
    vector<string> res;
    auto dfs = [&](auto& dfs, string s, char last) {
      if (s.size() == N) {
        res.push_back(s);
        return;
      }
      for (char c = 'a'; c <= last; c++) {
        dfs(dfs, s + c, (c == last) ? c + 1 : last);
      }
    };
    dfs(dfs, "", 'a');
    for (auto& x : res) cout << x << endl;
  }
  return 0;
}


Measured memory_bytes: 7796
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int X = in.nextInt();
		int x[]=new int[N];
		int c[]=new int[N];

		
		for(int i=0;i<N;i++) {
			x[i]=in.nextInt();
			c[i]=x[i]-X;
		}
		int min=Math.abs(c[0]);
		int temp;
		int b=Math.abs(c[0]);
		int a;
		for(int i=1;i<N;i++) {
			a=c[i];
			  while((temp=a%b)!=0){
				    a = b;
				    b = temp;
				  }

			min=Math.abs(Math.min(min, b));
		}
		
		System.out.println(min);

	}
}

Measured memory_bytes: 47960
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;

public static class P
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var s = Console.ReadLine();
        Console.WriteLine(Regex.Matches(s, "ABC").Count);
    }
}


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

typedef long long ll;
typedef long double ld;
#define size(a) int((a).size())
#define present(c, x) (c.find(x) != c.end()) 
#define printArray(arr) for (int i = 0; i<size(arr); i++) cout << arr[i] << '\n';cout << '\n'
#define printVerdict(verdict) cout << (verdict ? "YES": "NO") << '\n'
#define printDecimal(d) printf("%.9f\n", d)
#define inrange(val, start, end) (val >= start && val <= end)

const int inf = 0x3f3f3f3f;

template <class T1, class T2, class T3> 
void printTuple(tuple<T1, T2, T3> t) {cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << '\n';}
template <class T1, class T2>
void printPair(pair<T1, T2> p) {cout << p.first << " " << p.second << '\n';}
template <class T>
bool triangle(T a, T b, T c) {
	if (a + b <= c || a + c <= b || b + c <= a || a==b || b==c || c==a) return false;
	return true;
}


int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll x,k,d; cin >> x >> k >> d;
	ll possible = abs(x)%d, steps = abs(x)/d;
	if (steps >= k) cout << abs(x) - k*d << '\n';
	else {
		if ((k-steps) & 1) {
			if (x < 0) possible = min(abs(-possible + d), abs(-possible - d));
			else possible = min(abs(possible -d), abs(possible + d));
		}
		cout << possible << '\n';
	}
	
}



Measured memory_bytes: 3660
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
a = [x[i+1] - x[i] for i in range(n-1)]
b = [y[i+1] - y[i] for i in range(m-1)]

MOD = int(1e9+7)
ai = sum([a[i] * (i+1) * max((0, (n-1-i))) % MOD for i in range(n-1)])
bi = sum([b[i] * (i+1) * max((0, (m-1-i))) % MOD for i in range(m-1)])
ans = ai * bi % MOD
print(ans)


Measured memory_bytes: 23096
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a , b;
    cin >> a >> b;
    cout << max( 0 , a - b );
}




Measured memory_bytes: 256
import java.util.*;

/**
 * Main
 */
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int r = sc.nextInt();
		int D = sc.nextInt();
		int X[] = new int[11];
		X[0] = sc.nextInt();

		for (int i = 1; i <= 10; i++) {
			X[i] = X[i - 1] * r - D;
			System.out.println(X[i]);
		}
		sc.close();
	}
};


Measured memory_bytes: 35812
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N;
    cin >> N;
    string s;
    cin >> s;
    string t;
    cin >> t;
    int max_length = 0;
    for (int i = 1; i <= N; i++){
        if (s.substr(N - i, i) == t.substr(0, i)) max_length = i;
    }
    cout << 2 * N - max_length << endl;
}


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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int m, d;
    cin >> m >> d;
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= d; j++) {
            int d10 = (j / 10);
            int d1 = (j % 10);
            
            ans += (d1 >= 2 && d10 >= 2 && d1 * d10 == i);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInteger = readLn :: IO Integer
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = do
	[ x, y ] <- readInts
	putStrLn $ which "No" "Yes" $ null $ do
		i <- [ 0 .. x ]
		let
			j = x - i
		guard $ i * 2 + j * 4 == y
		return ()

Measured memory_bytes: 3736