akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

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

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

using P1 = array<int, 26>;
using P2 = array<char, 365>;

int ii = 365;
struct state{
    array<int, 26> prv;
    array<char, 365> ans;
    int val1, val2;
    bool operator<(const state &a) const { return val1+val2*2 > a.val1+a.val2*2; }
    state(P1 a, P2 b, int x, int y) : prv(a), ans(b), val1(x), val2(y) {};
};


int main() {
    int d;
    cin >> d;
    array<int, 26> A{};
    for (auto &&k : A) cin >> k;
    vector<array<int, 26>> v(d);
    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < 26; ++j) {
            scanf("%d", &v[i][j]);
        }
    }
    vector<int> ans(d);
    int W = 400;
    vector<state> a;
    a.emplace_back(P1{}, P2{}, 0, 0);
    fill(a[0].prv.begin(),a[0].prv.end(), -1);
    for (int i = 0; i < d; ++i) {
        ii--;
        priority_queue<state> Q;
        for (auto &&s : a){
            s.val2 = 0;
            for (int l = 0; l < 26; ++l) {
                s.val1 -= (i-s.prv[l])*A[l];
                s.val2 -= (i-s.prv[l])*A[l];
            }
            for (int k = 0; k < 26; ++k) {
                state ss(s);
                ss.ans[i] = k;
                ss.val1 += v[i][k]+s.prv[k]*A[k];
                ss.val2 += s.prv[k]*A[k];
                ss.prv[k] = i;
                ss.val1 -= s.prv[k]*A[k];
                ss.val2 -= s.prv[k]*A[k];
                Q.emplace(ss);
                if(Q.size() > W) Q.pop();
            }
        }
        a.clear();
        while(!Q.empty()) a.emplace_back(Q.top()), Q.pop();
    }
    sort(a.begin(),a.end(), [&](state a, state b){ return a.val1 < b.val1; });
    for (auto &&m : a.back().ans) {
        printf("%d\n", m+1);
    }
    return 0;
}

Measured memory_bytes: 4100
#include <iostream>
#include <array>
#include <algorithm>

int main(void) {
    std::array<u_int, 10> heights;

    for (u_int i = 0; i < 10; ++i) {
        std::cin >> heights[i];
    }

    std::sort(heights.begin(), heights.end(), std::greater<u_int>());
    for (u_int i = 0; i < 3; ++i) {
        std::cout << heights[i] << std::endl;
    }

    return 0;
}

Measured memory_bytes: 1164
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
#define forn(a, e) for (i64 a = 0; a < (i64)(e); a++)
#define forr(a, s, e) for (i64 a = s; a < (i64)(e); a++)
#define fore(e, a) for (auto& e : a)

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; fore(e, a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; fore(e, a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; fore(r, a) { fore(e, r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; fore(e, a) { cerr << e.field << " ";} cerr << "\n"; }
#define logvff(a, f1, f2) {cerr << #a".{"#f1 << ", "#f2 << "} = \n"; fore(e, a) { cerr << "(" << e.f1 <<", " << e.f2 << ") ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logvff(a, f1, f2)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

using iip = pair<int, int>;
using llp = pair<i64, i64>;
using ivec = vector<int>;
using llvec = vector<i64>;
using svec = vector<string>;
template<typename T> using vec = vector<T>;

template<typename T, typename Dim>
auto make_vec(T value, Dim dim) { return vector<T>(dim, value); }
template<typename T, typename Dim1, typename... Dim>
auto make_vec(T value, Dim1 dim1, Dim... dims) { return make_vec(make_vec(value, dims...), dim1); }

template<typename T>
bool uax(T& v, const T& newv) { if (v < newv) { v = newv; return true; } else return false; }
template<typename T>
bool uin(T& v, const T& newv) { if (v > newv) { v = newv; return true; } else return false; }

template<typename T>
istream& operator>>(istream& is, vector<T>& c) { for (auto& e : c) is >> e; return is; }
template<typename T, size_t N>
istream& operator>>(istream& is, array<T, N>& c) { for (auto& e : c) is >> e; return is; }

template<typename ...T>
istream& read(T&... args) { return (cin >> ... >> args); }

static mt19937 rande(123123);
template<typename T>
T rand_int(T from, T to) { uniform_int_distribution<T> distr(from, to); return distr(rande); }

const i64 INF = 1e18;
const i64 M = 1e9 + 7;
const int MXB = 20;
using bin = bitset<MXB + 1>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    rande.seed(chrono::steady_clock::now().time_since_epoch().count());

    int x, p;
    while (read(x, p)) {
        double ans = 100.0 * ((x + 1) / 2) / (p);
        cout << fixed << setprecision(20);
        cout << ans << endl;
    }
}

Measured memory_bytes: 3828
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define pai 3.14159265358979323846
ll gcd(ll a, ll b){if (a%b == 0)  return(b);else  return(gcd(b, a%b));}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
/* map<string,int> */
/* 大文字を小文字に変換 tolower*/
/* 小文字を大文字に変換 toupper*/
/* 辞書順 next_permutation(a.begin(),a.end()) */
 
int main() {
	int n;
	cin >> n;
	vector <ll> a(100*100*100,0);
	for(int x =1;x <= 100; x++) {
		for(int y =1;y<=100;y++) {
			for(int z =1;z<=100;z++) {
				int tmp = x * x + y*y+z*z + x*y + y*z + z*x;
				a[tmp]++;

			}
		}
	}
	for(int i =1;i <=n;i++) {
		cout << a[i] << endl;
	}
}

Measured memory_bytes: 10692
#include <bits/stdc++.h>
using namespace std;
pair<long long,long long> dp[3001][3001];
/*int rec(int i,int j,vector<int> &v,int cnt){
   
    if(i>j)
    return 0;
    int a=0,b=0;
    if(cnt%2==0){
    a=max((v[i]+rec(i+1,j,v,cnt++)),v[j]+rec(i,j-1,v,cnt++));
    }
    else{
    b=max((v[i]+rec(i+1,j,v,cnt++)),v[j]+rec(i,j-1,v,cnt++));
    }
    cout<<a<<" "<<b<<endl;
    ans=min(ans,a-b);
    return ans;
}
*/

int main() {
    int n;
    cin>>n;
    vector<long long> v;
    
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        v.push_back(x);
    }


  for(int i=0;i<n;i++){
      dp[i][i].first=v[i];
      dp[i][i].second=0;
  }
  int k=n-1;
  for(int j=1;j<n;j++){
      int l=j;
     for(int i=0;i<k;i++){

         long long a=v[l]+dp[i][l-1].second;
         long long b=v[i]+dp[i+1][l].second;
        
         if(a>b){
             dp[i][l].first=v[l]+dp[i][l-1].second;
             dp[i][l].second=dp[i][l-1].first;
         }
         else{
             dp[i][l].first=v[i]+dp[i+1][l].second;
             dp[i][l].second=dp[i+1][l].first;
         }
         l++;
     }
     k--;
  }
  long long ans=dp[0][n-1].first-dp[0][n-1].second;
  cout<<ans<<endl;
}


Measured memory_bytes: 85416
#include <iostream>
#include <cmath>

using namespace std;

int N;
int A, B;

int sum_of_row(int num) {
	int sum = 0;
	while (num > 0) {
		sum += num % 10;
		num /= 10;
	}

	return sum;
}

int main() {
	cin >> N >> A >> B;
	int sum = 0;
	for (int a = 0; a <= N; a++) {
		if (A <= sum_of_row(a) && sum_of_row(a) <= B) {
			sum+=a;
		}
	}

	cout << sum << endl;
	return 0;
}



Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;

public class Main {
    static int gcd(int a,int b){
        if(b==0)
            return a;
        return gcd(b,a%b);
    }
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int i,j;
        int n=in.nextInt();
        long sum=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                for(int k=1;k<=n;k++) {
                    int x = gcd(j, k);
                    sum+=gcd(x,i);
                }

            }
        }

        System.out.println(sum);

    }
}

class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}





Measured memory_bytes: 32388
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

typedef long long ll;

map<ll,int> x2id;
map<ll,int> y2id;
ll id2x[60];
ll id2y[60];

struct P {
  ll x, y;
};

P ps[60];
int cs[60][60];

int main(void) {
  int n, k;
  scanf("%d%d", &n, &k);
  REP(i, n) {
    scanf("%lld%lld", &ps[i].x, &ps[i].y);
    id2x[i] = ps[i].x;
    id2y[i] = ps[i].y;
  }
  id2x[n+1] = 1000000000 + 1;
  id2y[n+1] = 1000000000 + 1;
  sort(id2x, id2x + n+1);
  sort(id2y, id2y + n+1);
  REP(i, n+1) {
    x2id[id2x[i]] = i;
    y2id[id2y[i]] = i;
  }
  REP(ix, n+1) {
    REP(iy, n+1) {
      ll x = id2x[ix];
      ll y = id2y[iy];
      int cnt = 0;
      REP(i, n) {
        if(ps[i].x <= x && ps[i].y <= y) {
          ++cnt;
        }
      }
      cs[ix+1][iy+1] = cnt;
    }
  }
  ll res = 4e18;
  REP(ix2, n+1) {
    REP(ix1, ix2) {
      REP(iy2, n+1) {
        REP(iy1, iy2) {
          int cnt = cs[ix2+1][iy2+1] - cs[ix2+1][iy1] - cs[ix1][iy2+1] + cs[ix1][iy1];
          // cerr << cnt << " " << endl;
          if(cnt == k) {
            ll area = (id2x[ix2] - id2x[ix1]) * (id2y[iy2] - id2y[iy1]);
            if(area < res) {
              res = area;
            }
          }
        }
      }
    }
  }
  printf("%lld\n", res);
  return 0;
}


Measured memory_bytes: 256
x1,y1,x2,y2 = map(int, input().split())

x12 = x2-x1
y12 = y2-y1

x23 = -y12
y23 = x12

x34 = -y23
y34 = x23

x3 = x2 + x23
x4 = x3 + x34
y3 = y2 + y23
y4 = y3 + y34

print(x3,y3,x4,y4)

Measured memory_bytes: 38384
//
// Created by kuribohkute on 29/12/2018.
//

#include <vector>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

typedef long long cc;

bool was[10];

int main() {

    string s;
    cin >> s;
    int n = (int)s.size();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            string t = "";
            for (int l = 0; l < n; l++) {
                if (l <= i || l >= j) {
                    t += s[l];
                }
            }
            if (t == "keyence") {
                cout << "YES";
                return 0;
            }
        }
    }
    cout << "NO";

    return 0;
}

Measured memory_bytes: 256
N = int(input())

L =[1,6**1,6**2,6**3,6**4,6**5,6**6,9**1,9**2,9**3,9**4,9**5]
X = [0]*(N+1)
for i in range(1, N+1):
    X[i] = 100000

for i in range(N+1):
    for l in L:
        if i+l <= N:
            X[i+l] = min(X[i] + 1, X[i+l])
        
print(X[-1])


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e17;
const int inf = 1e5;
//typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      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[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        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(){
  ll N; cin>>N;
  ll now=100;
  for(int i=1 ; i<=4000; i++){
    now *=1.01;
    if(now>=N){
      cout<<i<<endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 3620
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007LL
#define llMAX 9223372036854775807LL
#define llMIN -9223372036854775808LL
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

int main(){
  ll ans=0;
  cin >> n ;
  cout<<(n+n*n+n*n*n)<<endl;
  return 0;
}

Measured memory_bytes: 3592
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;

//https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let mut map = HashMap::new();
    for _ in 0..n{
        let count = map.entry(read::<u64>()).or_insert(0);
        *count += 1;
    }

    let mut counts:Vec<(u64,u64)> = Vec::new();
    for (k,v) in map.iter(){
        counts.push((*k,*v));
    }
    counts.sort_by(|a,b| b.0.partial_cmp(&a.0).unwrap());

    let mut ans: Vec<u64> = Vec::new();
    for v in counts.iter(){
        if v.1 >= 4{
            ans.push(v.0);
            ans.push(v.0);
            break;
        }else if 2 <= v.1 && v.1 < 4{
            ans.push(v.0);
            if ans.len() >= 2{
                break;
            }
        }
    }

    if ans.len() >= 2 {
        println!("{}",ans[0]*ans[1]);
    }else{
        println!("0");
    }

}


Measured memory_bytes: 6728
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	int c;
	for(int i=0;i<=9999;i++){
		if(int(i*0.08)==a&&int(i*0.1)==b){
			c=i;
			break;
		}
		if(int(i*0.08)!=a||int(i*0.1)!=b){
			c= -1;
			continue;
		}
	}
	cout<<c;
} 

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

int main(){
    int x[5];
    for(int i=0;i<5;i++){
        cin>>x[i];
    }
    for(int i=0;i<5;i++){
        if(x[i]!=i+1){
            cout<<i+1<<"\n";
        }
    }
}
                                                                              
                                                                              
                                                                              
                                                                              
                                                                              
                                                                              
                                                                              
                                                                              

Measured memory_bytes: 3576
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())

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

lst=[[A[0],0,1]]
count=0

for i in range(1,N):
    m=1
    while lst and lst[-1][0]>A[i]:
        a,b,c=lst.pop()
        count+=a*(i-b)*c
        m+=c
    lst.append([A[i],i,m])
while lst:
    a,b,c=lst.pop()
    count+=a*(N-b)*c

print(count)


Measured memory_bytes: 122828
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
//#include<map>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define izryt bool
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const llint mod=1000000007;
const llint gya=500000004;//mod modで2の逆元
const llint big=1e9+1e8;
const llint red=0xE869120;
const llint pro=1002001;
int main(void){
	int a[12]={0,2,0,1,0,1,0,0,1,0,1,0};
	int x,y;
	cin>>x>>y;x--;y--;
	if(a[x]==a[y]){cout<<"Yes"<<endl;}
	else{cout<<"No"<<endl;}
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input("").split(" "))
 
cnt = 0
for i in range(K, N+2):
  start_idx = 0
  end_idx = 0
  #for j in range(i):
  #  start_idx += j
  start_idx = (i-1) * (i)//2
  
  #for j in range(i):
  #  end_idx += (N-j)
  end_idx = (i)*N - start_idx 
    
  #print( end_idx - start_idx+1)
  cnt += (end_idx - start_idx+1)
  cnt %= (10**9+7)
  
  
print(cnt%(10**9+7))

Measured memory_bytes: 9192
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=505;
const LL INF=1e18;
int n;
int a[N][N];
LL f[N][N],g[N][N];
LL dp[N][N];
int main(){
	n=read();
	For(i,1,n)
		For(j,1,n)
			if (i!=j)
				a[i][j]=read();
	For(i,1,n){
		For(j,i+1,n){
			f[i][j]=f[i][j-1];
			g[i][j]=g[i][j-1];
			For(k,i,j){
				f[i][j]-=a[k][j];
				g[i][j]+=a[j][k];
			}
		}
	}
//	outtag(a);
//	For(i,1,n){
//		For(j,1,n){
//			printf("%d ",a[i][j]);
//		}
//		puts("");
//	}
//	outtag(f);
//	For(i,1,n){
//		For(j,1,n){
//			printf("%lld ",f[i][j]);
//		}
//		puts("");
//	}
//	outtag(g);
//	For(i,1,n){
//		For(j,1,n){
//			printf("%lld ",g[i][j]);
//		}
//		puts("");
//	}
	For(i,0,N-1)
		For(j,0,N-1)
			dp[i][j]=-INF;
	dp[1][1]=-f[1][n];
	LL ans=-INF;
	For(i,1,n)
		For(j,1,n){
//			printf("dp[%d][%d] = %lld\n",i,j,dp[i][j]);
			if (i<=j){
				ans=max(ans,dp[i][j]+f[i][n]+g[j][n]);
//				if (i<j)
//					dp[j+1][j]=max(dp[j+1][j],dp[i][j]+f[i][j-1]-a[j-1][j]-a[j][j+1]);
				For(k,j+1,n){
					dp[k][i]=max(dp[k][i],dp[i][j]+f[i][k-1]-g[i][j]);
//					For(t,j,n)
//						dp[k][t]=max(dp[k][t],dp[i][j]+f[i][k-1]-g[i][j]+g[i][t]);
				}
			}
			else {
				For(k,i,n)
					dp[i][k]=max(dp[i][k],dp[i][j]+g[j][k]);
			}
		}
	cout<<g[1][n]-f[1][n]-ans<<endl;
	return 0;
}
/*
5
14 16 3 3
15 5 7 19
14 9 0 11
14 5 8 2
9 0 4 18
*/

Measured memory_bytes: 7168
#include<stdio.h>
#include<string.h>

#define N 550

int main(void)
{
	char s[N][N],a[N];
	int n,l,i,j;
	scanf("%d%d",&n,&l);
	for(i=0;i<n;i++){
		scanf("%s",s[i]);
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(strcmp(s[j-1],s[j])>0){
				strcpy(a,s[j-1]);
				strcpy(s[j-1],s[j]);
				strcpy(s[j],a);
			}
		}
	}
	for(i=0;i<n;i++){
		printf("%s",s[i]);
	}
	printf("\n");
	return 0;
}


Measured memory_bytes: 256
import collections
N=int(input())
A=[int(x) for x in input().split()]
AA=sorted(A)
c=collections.Counter(A)
t=N//3
ans="No"
if all(a==0 for a in A):
  ans="Yes"
elif len(c)==2 and N%3==0:
  if all(a==0 for a in AA[:t]):
    ans="Yes"     
elif len(c)==3 and N%3==0:
  if A.count(AA[0])==t and A.count(AA[t])==t:
    if AA[0]^AA[t]==AA[2*t] and AA[t]^AA[2*t]==AA[0] and AA[2*t]^AA[0]==AA[t]:
      ans="Yes"   
print(ans)

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

int main() {
	int n;
	cin >> n;
	vector<int>p(n);
	for (int i = 0; i < n; i++)cin >> p.at(i);
	sort(p.begin(), p.end());
	ll ans = 0;
	for (int i = 0; i < n - 1; i++)ans += p.at(i);
	ans += p.at(n - 1) / 2;
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < 3; ++i) {
		if (s[i] == s[i + 1]) {
			cout << "Bad" << endl;
			return 0;
		}
	}
	cout << "Good" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int gcd(int a, int b)
{
	return (b > 0)? gcd(b , a % b) : a;
}

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


int main()
{
	int a, b;
	
	
	while(cin >> a >> b)
	{
		cout << gcd(a, b) << " " << lcm(a, b) << endl;
	}

	
	return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

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

int main() {
  ll n, m; cin >> n >> m;
  vector<pair<ll, ll>> p(n);

  REP(i, n){
    ll a, b; cin >> a >> b;
    p[i] = make_pair(a, b);
  }

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

  ll ans = 0LL;
  for(const auto& x: p){
    if(m <= x.second){
      ans += x.first * m;
      break;
    }
    m -= x.second;
    ans += x.first * x.second;
  }

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


Measured memory_bytes: 1792
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 input_vec() -> Vec<i64> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn calc(contest: usize, day_idx: i64, last: &Vec<i64>, c_vec: &Vec<i64>, scores: &Vec<Vec<i64>>) -> i64 {
    let mut score = scores[day_idx as usize][contest];
    for i in 0..26 {
        if i == contest {
            continue;
        }
        score -= c_vec[i] * (day_idx + 1 - last[i]);
    }
    score
}

fn simulate(day_idx: i64, last: &Vec<i64>, c_vec: &Vec<i64>, scores: &Vec<Vec<i64>>) -> usize {
    let mut max = std::i64::MIN;
    let mut max_indices = vec![0; 3];
    let mut c_vec_sum = 0;
    for c in c_vec {
        c_vec_sum += c;
    }
    for contest1 in 0..26 {
        for contest2 in 0..26 {
            for contest3 in 0..26 {
                let mut last_buf = last.to_vec();
                let mut sum = 0;
                sum += calc(contest1, day_idx, &last_buf, c_vec, scores);
                last_buf[contest1] = day_idx;
                if day_idx + 1 < scores.len() as i64 {
                    sum += scores[day_idx as usize][contest2];
                    last_buf[contest2] = day_idx + 1;
                }
                if day_idx + 2 < scores.len() as i64 {
                    sum += calc(contest3, day_idx + 2, &last_buf, c_vec, scores);
                    last_buf[contest3] = day_idx + 2;
                }
                if sum > max {
                    max = sum;
                    max_indices[0] = contest1;
                    max_indices[1] = contest2;
                    max_indices[2] = contest3;
                }
            }
        }
    }
    max_indices[0]
    // max
}

fn greedy(d: i64, c_vec: &Vec<i64>, scores: &Vec<Vec<i64>>) -> Vec<usize> {
    let mut last = vec![0; 26];
    let mut schedule: Vec<usize> = Vec::new();

    for day_idx in 0..d {
        let target = simulate(day_idx, &last, c_vec, scores);
        last[target] = day_idx + 1;
        schedule.push(target);
    }
    schedule
}

fn main() {
    let d: i64 = input();
    let c_vec = input_vec();
    let mut scores: Vec<Vec<i64>> = Vec::new();
    for _ in 0..d {
        let score = input_vec();
        scores.push(score);
    }
    for i in greedy(d, &c_vec, &scores) {
        println!("{}", i + 1);
    }
}


Measured memory_bytes: 2244
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdio.h>
#include<vector>
#include<map>
using namespace std;

int N,H[21];
int ans;

int main() {
	cin >> N;
	cin >> H[0];
	ans = 1;
	for (int i = 1; i < N; i++) {
		cin >> H[i];
		if (H[0] <= H[i]) {
			ans++;
			H[0] = H[i];
		}
	}


	cout << ans << endl;

	return 0;
}

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

typedef  long long ll;
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//
//
#define int long long

using namespace std;

int ctoi(char c) {
 switch (c) {
 case '0': return 0;
 case '1': return 1;
 case '2': return 2;
 case '3': return 3;
 case '4': return 4;
 case '5': return 5;
 case '6': return 6;
 case '7': return 7;
 case '8': return 8;
 case '9': return 9;
 default: return 0;
 }
}


 ll  a,b,c,s,t,i,j,k,x,y,z;
 ll A,B,C,S,T,X,Y,Z;
 ll count;
signed main(){
	
	cin>>x>>y;
	if( x<=y ) cout<<"unsafe";
	else cout<<"safe";

 return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<pair<int, int>> x(N), y(N);
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    x[i] = make_pair(a, i);
    y[i] = make_pair(b, i);
  }
  sort(x.begin(), x.end());
  sort(y.begin(), y.end());

  vector<vector<pair<int, int>>> G(N, vector<pair<int, int>>());
  for (int i = 1; i < N; i++) {
    G[x[i].second].push_back(
        make_pair(x[i].first - x[i - 1].first, x[i - 1].second));
    G[x[i - 1].second].push_back(
        make_pair(x[i].first - x[i - 1].first, x[i].second));
    G[y[i].second].push_back(
        make_pair(y[i].first - y[i - 1].first, y[i - 1].second));
    G[y[i - 1].second].push_back(
        make_pair(y[i].first - y[i - 1].first, y[i].second));
  }

  ll ret = 0;
  vector<bool> used(N);
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      que;
  que.push(make_pair(0, 0));
  while (!que.empty()) {
    int cost = que.top().first, v = que.top().second;
    que.pop();
    if (used[v]) continue;
    used[v] = true;
    ret += cost;
    for (int i = 0; i < G[v].size(); i++) {
      que.push(make_pair(G[v][i].first, G[v][i].second));
    }
  }
  cout << ret << endl;
}

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

#define ll long long
// #define MULTI_TEST

void solve() {
	string s;
	cin >> s;
	if(s[0] == 'S') cout << "Cloudy";
	else if(s[0] == 'C') cout << "Rainy";
	else cout << "Sunny";
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
#ifdef MULTI_TEST
	int t;
	cin >> t;
	while(t--) {
		solve();
		cout << "\n";
	}
#else
	solve();
	cout << "\n";
#endif

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <cmath>
#include <cstdio>
using namespace std;
typedef complex<double> xy_t;
xy_t P[110];
const double eps = 1e-11;

double cross_product(xy_t a , xy_t b){
	return (conj(a)*b).imag();
}


int main(){
	int i,t,n;
	double x,y,area;
	scanf("%d\n",&n);
	for(t=0;t<n;t++){
		for(i=0;i<4;i++){
			scanf("%lf %lf\n",&x,&y);
			P[i]= xy_t(x,y);
		}
		area = cross_product(P[1]-P[0],P[3]-P[2])/2;;
		bool p = abs(area)<eps;
		cout << (p ? "YES" : "NO") << endl;
	}

	return 0;
}

Measured memory_bytes: 1244
// Package main provides
//
// File:  a.go
// Author: ymiyamoto
//
// Created on Fri Dec 28 14:56:46 2018
//
package main

import "fmt"

func main() {
	var A, B, X int
	fmt.Scan(&A, &B, &X)
	if A <= X && X <= A+B {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

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

    int n;
    cin >> n;
    vector<int> cnt(13, 0);
    cnt[0] = 1;
    for(int i = 0; i < n; ++i){
        int d;
        cin >> d;
        ++cnt[d];
    }
    
    if(cnt[0] >= 2 || cnt[12] >= 2){
        cout << 0 << endl;
        return 0;
    }
    vector<int> plural;
    vector<int> single;
    for(int i = 1; i < 12; ++i){
        if(cnt[i] >= 3){
            cout << 0 << endl;
            return 0;
        }
        if(cnt[i] == 0) continue;

        if(cnt[i] == 1) single.push_back(i);
        else    plural.push_back(i);
    }

    int p = plural.size();
    int s = single.size();
    int ans = 0;
    for(int bit = 0; bit < (1 << s); ++bit){
        vector<int> time;
        time.push_back(0);
        if(cnt[12]) time.push_back(12);
        for(int i = 0; i < p; ++i){
            time.push_back(plural[i]);
            time.push_back(24 - plural[i]);
        }
        for(int i = 0; i < s; ++i){
            if((bit >> i) & 1)  time.push_back(single[i]);
            else    time.push_back(24 - single[i]);
        }
        int sz = time.size();
        int mingap = INF;
        for(int i = 0; i < sz; ++i){
            for(int j = 0; j < sz; ++j){
                if(i == j)  continue;
                int gap = abs(time[i] - time[j]);
                chmin(mingap, min(gap, 24 - gap));
            }
        }
        chmax(ans, mingap);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int L, R;
    long long tmp;
    int a = 2019;
    cin >> L >> R;
    if(R - L >= 2018 || L == 0){
        a = 0;
    }else{
        for(int i=L%2019;i < 2019; i++){
            for(int j=i+1;j<= R%2019;j++){
                tmp = (i%2019) * (j%2019);
                tmp %= (long long)2019;
                a = min((int)tmp, a);
            }
        }
    }
    cout << a << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)

int main() {
  int N;
  string S;
  cin >> N;
  cin >> S;
  if(N%2 == 1) {
    cout << "No" << endl;
    return 0;
  }
  
  rep(i,N/2) {
    if( S[i] != S[N/2+i] ) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine().Split(' ');
            Console.WriteLine(S[1] + S[0]);

        }

    }
    
}


Measured memory_bytes: 11092
#include<iostream>
using namespace std;
int main(){
	
	int n, m, x, y, a, b;
	cin >>n >>m >>x >>y;
	
	for(int i=0; i<n; i++){
		
		cin >>a;
		if(a>x) x=a;
		
	}
	for(int i=0; i<m; i++){
		
		cin >>b;
		if(b<y) y=b;
		
	}
	
	cout <<(x<y?"No ":"") <<"War" <<endl;
	
}

Measured memory_bytes: 256
import java.util.*;
import java.math.*;

public class Main {
    private static long gcdThing(long a, long b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.longValue();
    }
    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            while (sc.hasNextLong()) {
                long a = sc.nextLong();
                long b = sc.nextLong();
                long c = gcdThing(a,b);
                System.out.printf("%d %d\n",c,a/c*b);
            }
        }
    }
}


Measured memory_bytes: 26568
import sys
k, n = map(int,input().split())
l = list(map(int,input().split()))
m = sys.maxsize

for i in range(n):
    if(i == 0):
        f = l[i-1] - l[0]
        s = (k - l[i+1]) + l[i]
    elif(i == n-1):
        f = l[i] - l[0]
        s = (k - l[i]) + l[i-1]
    else:
        f = l[i] + (k - l[i+1])
        s = (k - l[i]) + l[i-1]
    
    if(m > min(f,s)):
        m = min(f,s)

print(m)


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


int main() {
  int n, m;
  cin >> n >> m;
  vector<string> a(n), b(m);
  rep(i,n) cin >> a[i];
  rep(i,m) cin >> b[i];
  if(n==m) {
    rep(i,n) {
      if(a[i]!=b[i]) {
        cout << "No" << endl;
        return 0;
      }
      cout << "Yes" << endl;
      return 0;
    }
  }
  rep(i,n-m) {
    rep(j,n-m) {
      bool ok=true;
      rep(k,m) {
        rep(l,m) {
          if(a[i+k][j+l]!=b[k][l]) {
            ok=false;
            break;
          }
        }
        if(!ok) break;
      }
      if(ok) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

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

using namespace std;
int main(){
	int X, N;
	cin>>X>>N;
	int amt = 0;
	amt = X * 500;
	
	
	if((amt > N) || (amt == N)) {
	cout<<"Yes"<<endl;
}
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

#define int long long

#if defined(__GNUC__)
#define __int32 __int32_t
#endif // __GNUC__

#define itn __int32
#define REP(i, n) for(itn (i) = 0; (i) < (n); (i)++)
#define REP2(i, x, n) for(itn (i) = x; (i) < (n); (i)++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SORT(x) sort(ALL(x))
#define RSORT(x, T) sort(ALL(x), greater<(T)>())
#define REVERCE(x) reverce(ALL(x))

#define INT_POW(x, y) [](int a, int b){int c = a; REP(i, b - 1){c *= a;} return c;}(x, y)

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

	int n;

	cin >> n;

	vector<int> d(n);

	REP(i, n) {
		cin >> d[i];
	}

	if (d[0]) {
		cout << 0;
		return 0;
	}

	//if (n == 1) {
	//	cout << 1;
	//	return 0;
	//}

	int cnt = 1;
	
	vector<int> ren_set;

	SORT(d);

	int ren = 1;

	while(cnt < n){
		
		while (cnt < n && d[cnt] == d[cnt - 1]) {
			ren++;
			cnt++;
		}

		if (cnt < n && d[cnt] - 1 != d[cnt - 1]) {
			cout << 0;
			return 0;
		}

		ren_set.push_back(ren);
		if (cnt == n - 1) {
			ren_set.push_back(1);
		}
		ren = 1;
		cnt++;
	}

	if (ren_set[0] != 1) {
		cout << 0;
		return 0;
	}/*

	if (ren_set.size() == 1) {
		if (ren_set[0] == 1) {
			cout << 1;
			return 0;
		}
		cout << 0;
		return 0;
	}*/

	int res = ren_set[0];

	REP2(i, 1, ren_set.size()) {
		REP(j, ren_set[i]) {
			res *= ren_set[i - 1];
			res %= 998244353;
		}
		
	}

	cout << res;

	return 0;
}


Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Maxn=4e5+10;
//const ll Maxm=5e5+10;
const ll Mod=998244353;
ll l[Maxn],r[Maxn];
struct segment_tree{
    ll l,r,ls,rs,v,lazy_tag;
}T[Maxn<<2];
ll cnt,a[Maxn];
ll build(ll l,ll r){
    ll t=cnt++;
    T[t].lazy_tag=0;
    T[t].l=l;T[t].r=r;
    if(l!=r){
        ll mid=(l+r)>>1;
        T[t].ls=build(l,mid);
        T[t].rs=build(mid+1,r);
        T[t].v=T[T[t].ls].v+T[T[t].rs].v;
    }else{
        T[t].ls=T[t].rs=-1;
        T[t].v=a[l];
    }
    return t;
}
void push_down(ll v){
    ll mid=(T[v].l+T[v].r)>>1;
    ll l=T[v].l;    ll r=T[v].r;
    if(T[v].l!=T[v].r){
        T[T[v].ls].v=(T[T[v].ls].v+T[v].lazy_tag*(mid-l+1)%Mod+Mod)%Mod;
        T[T[v].rs].v=(T[T[v].rs].v+T[v].lazy_tag*(r-mid)%Mod+Mod)%Mod;
        T[T[v].ls].lazy_tag+=T[v].lazy_tag;
        T[T[v].rs].lazy_tag+=T[v].lazy_tag;
    }
    T[v].lazy_tag=0;
}
void change(ll l,ll r,ll tag,ll value){
    if(l>T[tag].r||r<T[tag].l) return;
    if(l<=T[tag].l&&T[tag].r<=r){
        T[tag].v=(T[tag].v+(T[tag].r-T[tag].l+1)*value%Mod+Mod)%Mod;
        T[tag].lazy_tag+=value;
        return;
    }
    push_down(tag);
    change(l,r,T[tag].ls,value);
    change(l,r,T[tag].rs,value);
    T[tag].v=(T[T[tag].ls].v+T[T[tag].rs].v+Mod)%Mod;
}
ll query(ll l,ll r,ll tag){
    if(l>T[tag].r||r<T[tag].l) return 0;
    if(l<=T[tag].l&&T[tag].r<=r)    return T[tag].v;
    push_down(tag);
    return (query(l,r,T[tag].ls)+query(l,r,T[tag].rs)+Mod)%Mod;
}
int main() {
    ll n,k;
    cin>>n>>k;
    for(ll i=1;i<=k;i++)    cin>>l[i]>>r[i];
//    for(ll i=1;i<=n;i++)    cin>>a[i];
    a[1]=1;
    build(1,n);
    for(ll i=1;i<=n;i++){
        ll temp=query(i,i,0);
        for(ll j=1;j<=k;j++){
            change(i+l[j],i+r[j],0,temp);
        }
    }
    cout<<query(n,n,0);
    return 0;
}

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

int main() {
  long long  N, K;
  cin >> N >> K;
  
  if(N % K == 0)
    cout << 0 << endl;
  else{
    long long d = N % K;
    if(abs(d-K) > d)
      cout << d << endl;
    else
      cout << abs(d-K) << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  int cnt = 0;
  for(int i = 0; i < n-1; i++){
    int p = i;
    for(int j = i; j < n; j++){
      if(a[j] < a[p]){
        p = j;
      }
    }
    if(p != i){
      swap(a[p], a[i]);
      cnt++;
    }
  }
  for(int k = 0; k < n; k++){
    if(k)cout << ' ';
    cout << a[k];
  }
  cout << endl;
  cout << cnt << endl;
}


Measured memory_bytes: 3112
#include <cstdio>
#include <cstdlib>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>

#define lli long


using namespace std;

char st[100001];
char *s = st;
int flag = 0;
int flag2 = 0;
int out = 0;

int dream(char *s){
	char *ss = "dream";
	while(*s && *ss && *s == *ss){
		s++;
		ss++;
	}
	if(*ss){
		return 0;
	}
	return 1;
}
int erase(char *s){
	char *ss = "erase";
	while(*s && *ss && *s == *ss){
		s++;
		ss++;
	}
	if(*ss){
		return 0;
	}
	return 1;	
}
int er(char *s){
	char *ss = "er";
	while(*s && *ss && *s == *ss){
		s++;
		ss++;
	}
	if(*ss){
		return 0;
	}
	return 1;	
}


int main(){
	scanf("%s",s);
	while(*s){
		if(dream(s)){
			s += 5;
			flag = 1;
			continue;
		}
		if(erase(s)){
			s+=5;
			flag2 = 1;
			continue;
		}
		if(flag && er(s)){
			s += 2;
			flag = 0;
			flag2 = 0;
			continue;
		}
		if(flag2 && *s == 'r'){
			s+=1;
			flag = 0;
			flag2 = 0;
			continue;
		}
		out = 1;
		break;



	}
	if(out){
		printf("NO\n");
	}else{
		printf("YES\n");
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<cstdlib>
using namespace std;

int S[199];

int top = 0;


int pop(){
  top = top - 1;
  return S[top + 1];
}

void push(int o){
  top = top + 1;
  S[top] = o;
}

int main(){

  int o1, o2;

  char *e = new char[100];



  while(cin >> e){

    if(e[0] == '+'){
      o1 = pop();
      o2 = pop();
      push(o1 + o2);
    }else if(e[0] == '-'){
      o1 = pop();
      o2 = pop();
      push(o2 - o1);
    }else if(e[0] == '*'){
      o1 = pop();
      o2 = pop();
      push(o2 * o1);
    }else{
      push(atoi(e));
    }
  }

  cout << S[top] << endl;

  delete[] e;

  return 0;
}



Measured memory_bytes: 3116
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		String s = sc.next();
		StringBuilder sb = new StringBuilder();
		sb.append("^");
		for(int i = 0 ; i < a ; i++) {
			sb.append("[0-9]");
		}
		sb.append("-");
		for(int i = 0 ; i < b ; i++) {
			sb.append("[0-9]");
		}
		sb.append("$");
		Pattern p = Pattern.compile(sb.toString());
		Matcher m = p.matcher(s);
		System.out.println(m.matches() ? "Yes" : "No");
		sc.close();

	}

}


Measured memory_bytes: 21840
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = list(map(int, input().split()))
B.sort()
C = list(map(int, input().split()))
C.sort()

ans = 0
for b in B:
    a_cnt = bisect.bisect_left(A,b)
    c_cnt = N-bisect.bisect_right(C,b)
    ans += a_cnt*c_cnt

print(ans)

Measured memory_bytes: 31444
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
ll mod = 1e9+7;
ll INF = 1e17;
/*ll gcd(ll a,ll b)
{
    if(a==0)
    return(b);
    return(gcd(b%a,a));
}*/
/*ll power(ll a,ll b,ll p)
{
	ll res=1;
	a%=p;
	while(b>0)
	{
		if(b&1)
		res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return(res);
}*/
/*void dfs(ll x)
{
	vis[x]=true;
	for(ll i=0;i<v[x].size();i++)
	{
		if(vis[v[x][i]]==false)
		dfs(v[x][i]);
	}
}*/
/*ll b_search(ll arr[],ll n,ll s)
{
	ll l=0,r=n-1;
	while(l<=r)
	{
		ll mid=l+(r-l)/2;
		if(arr[mid]==s)
		return(mid);
		if(arr[mid]<s)
		l=mid+1;
		else
		r=mid-1;
	}
	return(-1);
}*/
 
void solve()
{
	ll n;
	cin>>n;
	ll arr[n];
	for(ll i=0;i<n;i++)
	cin>>arr[i];
	ll cnt=0;
	ll m=INT_MAX;
	for(ll i=0;i<n;i++)
	{
		m=min(m,arr[i]);
		if(m==arr[i])
		cnt++;
	}
	cout<<cnt<<endl;
}
 
int main()
{
	IOS
	ll t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
    return(0);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char A,B;
  cin >> A >> B;
  
  if((A=='H' && B == 'H') || (A=='D' && B=='D')){
    cout << "H" << endl;
  }
  else{
    cout << "D" << endl;
  }
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    D = [[int(x) for x in input().split()] for _ in range(N)]

    ans = 0

    for a, b in D:
        if a == b:
            ans += 1
            if ans >= 3:
                print("Yes")
                return
        else:
            ans = 0


    print("No")

if __name__ == '__main__':
    main()



Measured memory_bytes: 9180
fun main (args : Array<String>) {
	
	val rs = readLine()
	val s = rs.toString()
	var revs = s.reversed()
	
	var rt : String = ""
	var t : String = ""
	
	for (str in revs) {
		rt += str
		
		if (rt in listOf("maerd")) {
			t += "maerd"
			rt = ""
		} else if (rt in listOf("remaerd")) {
			t += "remaerd"
			rt = ""
		} else if (rt in listOf("esare")) {
			t += "esare"
			rt = ""
		} else if (rt in listOf("resare")) {
			t += "resare"
			rt = ""
		} 
		
	}
	
	t = t.reversed()
	
	if (t == s) {
		println("YES")
	} else {
		println("NO")
	}
	
}

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

using namespace std;

int main(int argc, char const *argv[]) {
    int h, w, k;
    std::cin >> h >> w >> k;
    std::vector<std::string> field(h);
    for (size_t i = 0; i < h; i++) {
        std::cin >> field[i];
    }
    int bf = 0;
    int nVars = h + w;
    int nChoices = 0;
    while (bf <= ((1 << nVars) - 1)) {
        bitset<12> bs = bf;
        int nBlack = 0;
        for (size_t i = 0; i < h; i++) {
            if (!bs[i]) continue;
            for (size_t j = 0; j < w; j++) {
                if (!bs[h+j]) continue;
                if (field[i][j] == '#') nBlack++;
            }
        }
        if (nBlack == k) nChoices++;
        bf++;
    }
    std::cout << nChoices << '\n';
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// #define debug(a) cout << "["; rep(i,a.size()) cout << a[i] << ", "; cout<<"]"<< endl;

const ll mod = 1000000007;

int main() {
    int a,b,c; cin >> a >> b >> c;
    unordered_set<int> us;
    us.insert(a);
    us.insert(b);
    us.insert(c);
    if(us.size() == 2){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3644