akhauriyash/Code-Regression huggingface dataset:
def kmpTable(w):
    lw = len(w)
    nx = [-1] * (lw + 1)
    j = -1
    for i in range(lw):
        while j >= 0 and w[i] != w[j]:
            j = nx[j]
        j += 1
        nx[i + 1] = j
    return nx
def kmpSearch(s, w):
    ls = len(s)
    start = 0
    w_idx = 0
    ret = []
    nx = kmpTable(w)
    while start + w_idx < ls:
        if s[start + w_idx] == w[w_idx]:
            w_idx += 1
            if w_idx == len(w):
                ret.append(start)
                start = start + w_idx - nx[w_idx]
                w_idx = nx[w_idx]
        else:
            if w_idx == 0:
                start += 1
            else:
                start = start + w_idx - nx[w_idx]
                w_idx = nx[w_idx]
    return ret
T = input()
P = input()
ans = kmpSearch(T, P)
for i in ans:
    print(i)



Measured memory_bytes: 47924
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#include <bits/stdc++.h>
#include <cmath>
#define f first
#define s second
#define ms(a, b) memset(a,b,sizeof(a))
typedef long long ll;

using namespace std;

char _;
int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);

    int S,W;

    cin >> S >> W;

    (S<=W) ? cout << "unsafe" << "\n" : cout << "safe" << "\n";

    return 0;
}


Measured memory_bytes: 3660
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int s = scan.nextInt();
        List<Integer> list = new ArrayList<>();
        list.add(s);
        int index = 0;
        int ans = 0;
        while(true) {
        	int temp = list.get(index);
        	if(temp % 2 == 0) {
        		temp = even(temp);
        	}else {
        		temp = odd(temp);
        	}

        	if(list.contains(temp)) {
        		System.out.println(list.size() + 1);
        		return;
        	}
        	list.add(temp);
        	index++;
        }
    }
    public static int odd (int n) {
    	return 3 * n + 1;
    }
    public static int even(int n) {
    	return n / 2;
    }
}

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

#define int long long

const int M = 1e9 + 7, N = 2005;

int C[N][N];

int get(int n, int k) {
    if (k > n) return 0;
    if (k == 0) return n == 0;
    return C[n - 1][k - 1];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    C[0][0] = 1;
    for (int i = 1; i < N; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
    }
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        int kek = (get(n - k, i - 1) + get(n - k, i + 1)) % M;
        kek += get(n - k, i) * 2;
        kek %= M;
        cout << kek * get(k, i) % M << '\n';
    }
    return 0;
}


Measured memory_bytes: 30208
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;

int main(){

	long long N, M,d;

	d = 0;

	cin >> N;

	M = N;

	while(M>0){
		d += M % 10;
		M /= 10;
	}

	if( N % d == 0) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
	
	n=int(input())
	A=list(map(int,input().split()))
	B=reversed(list(map(int,input().split())))

	from itertools import accumulate
	A=list(accumulate(A))
	B = list(accumulate(B))  
	
	# この問題は長さが1-Nの連続部分の和の最大値を出せというものなので以下の通り
	ans=0
	for i in range(n):
		ans = max([A[i]+B[n-i-1] for i in range(n)])
	print(ans)
	
	
	
resolve()

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

double dp[301][301][301] = {};
int n;

double dfs(int i, int j, int k){
    if(dp[i][j][k] > 0) return dp[i][j][k];
    if(i+j+k == 0)  return 0;

    double ret = 1.0;
    if(i)   ret += (double)i / n * dfs(i-1, j, k);
    if(j)   ret += (double)j / n * dfs(i+1, j-1, k);
    if(k)   ret += (double)k / n * dfs(i, j+1, k-1);

    ret *= (double)n / (i+j+k);

    return dp[i][j][k] = ret;
}

int main(){
    cin >> n;

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

    cout << fixed << setprecision(12) << dfs(cnt[0], cnt[1], cnt[2]) << endl;

    return 0;
}

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

int dist[100000], indegree[100000] = {};
vector<int> adj[100000];

int dfs(int u) {
    if (dist[u] != -1)
        return dist[u];
    for (int v : adj[u])
        dist[u] = max(dist[u], dfs(v));
    dist[u]++;
    return dist[u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x-1].push_back(y-1);
        indegree[y-1]++;
    }

    memset(dist, -1, sizeof(dist));
    int ret = 0;
    for (int i=0; i<n; i++)
        if (indegree[i] == 0)
            ret = max(ret, dfs(i));

    cout << ret << "\n";

    return 0;
}


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

#define ms(s,n) memset(s,n,sizeof(s))
#define all(a) a.begin(),a.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mk make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;

const int MOD = (int) 1e9+7;
const int INF = (int) 1e9+1;
inline ll gcd(ll a,ll b){ll r;while(b){r=a%b;a=b;b=r;}return a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int n,x,t;
int main(){
	cin>>n>>x>>t;
	int res=n/x*t+min(1,n%x)*t;
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 3584
# -*- coding: utf-8 -*-
import statistics
import math
# 文字列の入力
N= int(input())
# 数値用のリスト　インプットをブランクで区切りリスト化
k = input()
l = [int(j) for j in k.split(" ")]
w = 0
# 算術平均値の取得
mean = round(statistics.mean(l))
for i in range(len(l)):
	w += (l[i] - mean) ** 2
print(w)

Measured memory_bytes: 5272
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

// Test Code
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
}

fn main() {
    println!("{}", solve(&stdin!()));
}

fn solve(src: &str) -> &str {
    input!{
        source = src,
        n: isize,
        m: isize,
    }
 
    if n == m {
        "Yes"
    } else {
        "No"
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define lol(i,n) for(int i=0;i<n;i++)
#define chmax(a,b) a=max(a,b);
typedef long long ll;
#define N 200010
class RAQxRMQ {
private:
	ll dat[2 * N], laz[2 * N];
	ll eval(ll k) {
		if (k < N) {
			laz[k * 2] += laz[k];
			laz[k * 2 + 1] += laz[k];
		}
		dat[k] += laz[k],laz[k]=0;
		return dat[k];
	}
public:
	void init() {
		lol(i, 2 * N)dat[i] = -1e17, laz[i] = 0;
	}
	void add(ll l, ll r, ll x) {
		l += N, r += N + 1;
		for (ll a = l, b = r; a < b; a >>= 1, b >>= 1) {
			if (a & 1)laz[a++] += x;
			if (b & 1)laz[--b] += x;
		}
		for (ll a = l, b = r; a + b; a >>= 1, b >>= 1) {
			dat[a / 2] = max(eval(a), eval(a ^ 1));
			dat[b / 2] = max(eval(b), eval(b ^ 1));
		}
	}
	ll maxi(ll l, ll r) {
		l += N, r += N + 1;
		for (ll d = 20; ~d; d--) {
			eval(l >> d); eval(r >> d);
		}
		ll res = -1e18;
		for (ll a = l, b = r; a < b; a >>= 1, b >>= 1) {
			if (a & 1)chmax(res, eval(a++));
			if (b & 1)chmax(res, eval(--b));
		}
		return res;
	}
	void upd(ll i, ll x) {
		ll val = maxi(i, i);
		add(i, i, max(0LL,x-val));
	}
};
ll n, d[N], q;
vector<ll> v[N];
int main() {
	cin >> n;
	lol(i, n)scanf("%lld",&d[i]);
	cin >> q;
	lol(i, q) {
		ll a, b; scanf("%lld%lld", &a, &b); a--;
		v[a].push_back(b);
	}
	RAQxRMQ seg; seg.init();
	seg.upd(0, 0);
	lol(i, n) {
		sort(v[i].begin(), v[i].end());
		for (auto to : v[i]) {
			seg.upd(to, seg.maxi(0, to - 1));
		}
		ll val = (d[i] == 0 ? -1 : +1);
		seg.add(i +1, n+1, val);
	}
	ll ans = -seg.maxi(0, n+1);
	lol(i, n)ans += d[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 16896
#include<iostream>
using namespace std;
int main()
{
	int n,a,b,c;
	cin>>n;
	a=n/100;
	b=n%100/10;
	c=n%10;
	if(a==1) a=9;
	else a=1;
	if(b==1) b=9;
	else b=1;
	if(c==1) c=9;
	else c=1;
	cout<<a<<b<<c;
}

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

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

  switch (d) {
  case 22:
    cout << "Christmas Eve Eve Eve" << endl;
    break;
  case 23:
    cout << "Christmas Eve Eve" << endl;
    break;
  case 24:
    cout << "Christmas Eve" << endl;
    break;
  case 25:
    cout << "Christmas" << endl;
    break;
  }
}

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

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

    string s; cin >> s;
    bool flag = false;
    for (int i = 0; i < s.size(); i++) {
        int ni = i+1, nni = i+2;
        if (0 <= ni && ni < s.size() && s[i] == s[ni]) {
            flag = true;
            cout << i+1 << " " << ni+1 << endl;
        } else if (0 <= nni && nni < s.size() && s[i] == s[nni]) {
            flag = true;
            cout << i+1 << " " << nni+1 << endl;
        }
        if (flag) break;
    }

    if (!flag) cout << "-1 -1" << endl;

    return 0;
}

Measured memory_bytes: 512
#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];
  bool b[n+1];
  for(int i=n;i>0;i--){
    int cur=0;
    for(int j=2*i;j<=n;j+=i){
      if(b[j]==true) cur++;
    }
    if(cur%2==a[i-1]) b[i]=false;
    else b[i]=true;
  }
  int ans=0;
  for(int i=1;i<=n;i++){
    if(b[i]) ans++;
  }
  cout<<ans<<endl;
  for(int i=1;i<=n;i++){
    if(b[i]) cout<<i<<" ";
  }
  cout<<endl;
}


Measured memory_bytes: 1920
#include <iostream>
#define eol '\n';
using namespace std;

class Node {
public:
  int id;
  int l;
  int r;
  int p;
  Node(): id(-1),l(-1),r(-1),p(-1){};
};

Node* tree;

void preorder(int id) {
  Node *node = &tree[id];
  
  cout << " " << node->id;
  
  if (node->l != -1) {
    preorder(node->l);
  }
  if (node->r != -1) {
    preorder(node->r);
  }
}

void inorder(int id) {
  Node *node = &tree[id];
 
  if (node->l != -1) {
    inorder(node->l);
  }

  cout << " " << node->id;

  if (node->r != -1) {
    inorder(node->r);
  }
}

void postorder(int id) {
  Node *node = &tree[id];
 
  if (node->l != -1) {
    postorder(node->l);
  }

  if (node->r != -1) {
    postorder(node->r);
  }

  cout << " " << node->id;
}

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

  int n,id,l,r;
  Node *node;

  cin >> n;
  tree = new Node[n];
  for (int i = 0; i < n; i++) {
    cin >> id >> l >> r;
    
    node = &tree[id];
    node->id = id;
    node->l  = l;
    node->r  = r;
    if (l != -1) {
      node = &tree[l];
      node->p = id;
    }
    if (r != -1) {
      node = &tree[r];
      node->p = id;
    }
  }

  int parent_id = -1;
  for (int i = 0; i < n; i++) {
    node = &tree[i];
    if (node->p == -1) {
      parent_id = i;
      break;
    }
  }

  cout << "Preorder" << eol;
  preorder(parent_id);
  cout << eol;
  cout << "Inorder" << eol;
  inorder(parent_id);
  cout << eol;
  cout << "Postorder" << eol;
  postorder(parent_id);
  cout << eol;
  
  return 0;
}

Measured memory_bytes: 1196
// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
#include "../debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

string S;

bool check_range(ll idx) { return 0 <= idx && idx < S.size(); }

void check(ll start, V<bool> &ok, ll goal) {
    ll now = start;
    while(true) {
        ll nxt = now;
        auto update = [&](ll nidx) {
            if(check_range(nidx) && nidx <= goal && S[nidx] == '.') {
                ok[nidx] = true;
                nxt = nidx;
            }
        };
        update(now + 1);
        update(now + 1 * 2);
        if(nxt == now) break;
        now = nxt;
    }
}

bool solve() {
    ll N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    cin >> S;
    A--;
    B--;
    C--;
    D--;
    V<bool> ok_a(N, false), ok_b(N, false);
    ok_a[A] = ok_b[B] = true;
    check(A, ok_a, C);
    check(B, ok_b, D);

    if(!ok_a[C] || !ok_b[D]) return false;

    if(D < C) {
        bool suc = false;
        for(ll i = 0; i < N - 2; i++) {
            if(ok_a[i] &&
               ok_b[i + 1] &&
               ok_a[i + 2]) {
                suc = true;
                break;
            }
        }
        if(!suc) return false;
    }

    return true;
}

int main() {
    cout << (solve() ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 592
//テ・ツ崢崚」ツ?、テ・ツュツ静ァツエツ?ヲツ閉ーテ」ツ?ョテ・ツ、ツァテ」ツ?催」ツ?陛」ツつ津ゥツ?催・ツ按療」ツ?ォテ・ツ?・テ」ツつ古」ツ?淌」ツつ欝ime Limit Exceededテ」ツ?ァテ」ツ?療」ツ??
//テァツ崢エテ」ツ?療」ツ?ヲテ」ツつづァツ崢エテ」ツ?療」ツ?ヲテ」ツつ５ime Limit Exceeded___テ」ツδ嘉」ツδ?」ツδ愿」ツ?ァテ」ツ??
//テ」ツつィテ」ツδゥテ」ツつケテ」ツδ暗」ツδ?」ツδ催」ツつケテ」ツ?ョテァツッツゥテ」ツつ津」ツ?凖」ツ?」テ」ツ?凝」ツつ甘・ツソツ佚」ツつ古」ツ?ヲテ」ツ??」ツ?セテ」ツ?療」ツ?淌」ツ??
//Respect2Dテ」ツ?陛」ツつ禿」ツ?ョテ」ツつウテ」ツδ。テ」ツδウテ」ツδ暗」ツつ津ィツヲツ凝」ツ?ヲテヲツーツ療」ツ?古」ツ?、テ」ツ?催」ツ?セテ」ツ?療」ツ?淌」ツ??

import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);

    static int[] prime = new int[10000001];
    // 0:テヲツ慊ェテ・ツ按、テ・ツョツ?
    // 1:テァツエツ?ヲツ閉ー
    // -1:テァツエツ?ヲツ閉ーテ」ツ?ァテ」ツ?ッテ」ツ?ェテ」ツ??

    public static void main(String[] args){

	prepare();

	while(true){
	    int n = kbd.nextInt();
	    if(n==0) break;
	    solve(n);
	}
    }

    static void prepare(){
	prime[0] = prime[1] = -1;
	int i=2;
	for(; i<prime.length; i++){
	    if(prime[i] == 0){
		prime[i] = 1;
		for(int j=i+i; j<prime.length; j+=i) prime[j]=-1;
	    }
	}
    }

    static void solve(int n){

	while(!(prime[n]==1 && prime[n-2]==1 && prime[n-6]==1 && prime[n-8]==1)){
	    n--;
	}
	System.out.println(n);
    }

    /*
    static boolean prime(int a){
	int k = (int)Math.sqrt(a);
	for(int l=2; l<=k; l++){
	    if(a%l == 0) return false;
	}
	return true;
    }
    */
}

Measured memory_bytes: 65020
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  ll N,A,B;
  cin>>N>>A>>B;
  
  if(A>B) co(0);
  else{
    if(N==1){
      if(A!=B) co(0);
      else co(1);
    }
    else{
      co((N-2)*(B-A)+1);
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
long long a[4010];
long long minn[4010][4010];
int main(){
	int n;
	long long x;
	scanf("%d%lld",&n,&x);
	for(int i=1;i<=n;i++) scanf("%lld",a+i),a[n+i]=a[i];
	for(int i=1;i<=2*n;i++)
		for(int j=i;j<=2*n;j++)
			if(j>i) minn[i][j]=min(minn[i][j-1],a[j]);
			else minn[i][j]=a[i];
	long long minans=1ll<<60;
	for(int i=0;i<n;i++){
		long long sum=0;
		for(int j=n+1;j<=2*n;j++)
			sum+=minn[j-i][j];
		sum+=i*x;
		minans=min(minans,sum);
	}
	printf("%lld",minans);
	return 0;
}

Measured memory_bytes: 125184
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		new Main().run();
	}

	private void run() {

		Scanner sc = new Scanner(System.in);

		int dir[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 } };

		while (true) {
			final int w = sc.nextInt();
			final int h = sc.nextInt();

			if (w == 0 && h == 0) {
				break;
			}

			final int amount = sc.nextInt();
			final int capacity = sc.nextInt();
			final int init = sc.nextInt();

			int[][] map = new int[h][w];

			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					map[i][j] = sc.nextInt();
				}
			}

			PriorityQueue<Walk> queue = new PriorityQueue<Walk>();
			for (int i = 0; i < w; i++) {
				Walk walk = new Walk(0, init, i, 0, h, w);
				walk.sanso--;
				queue.add(walk);
			}

			boolean flag = false;
			while (!queue.isEmpty()) {
				Walk walk = queue.poll();

				// System.out.println(walk.x + " " + walk.y + " " + walk.cost +
				// " " + walk.sanso);

				if (walk.sanso <= 0) {
					continue;
				} else if (walk.y >= h) {
					flag = true;
					System.out.println(walk.cost);
					break;
				}

				walk.visited[walk.y][walk.x] = true;

				if (map[walk.y][walk.x] <= 0) {
					walk.cost += (-map[walk.y][walk.x]);
				} else {
					walk.sanso = Math.min(map[walk.y][walk.x] + walk.sanso,
							capacity);
				}

				if (walk.cost > amount) {
					continue;
				}

				for (int i = 0; i < 3; i++) {
					if (walk.x + dir[i][0] >= 0
							&& walk.x + dir[i][0] <= w - 1
							&& walk.y + dir[i][1] >= 0
							&& walk.y + dir[i][1] <= h - 1
							&& !walk.visited[walk.y + dir[i][1]][walk.x
									+ dir[i][0]]) {

						Walk wa = new Walk(walk);
						wa.x += dir[i][0];
						wa.y += dir[i][1];
						wa.sanso--;
						queue.add(wa);
					} else if (i == 2 && walk.y == h - 1) {
						Walk wa = new Walk(walk);
						wa.y++;
						queue.add(wa);
					}
				}
			}

			if (!flag) {
				System.out.println("NA");
			}

		}
	}
}

class Walk implements Comparable<Walk> {
	int cost;
	int sanso;
	int x, y;
	boolean[][] visited;

	public Walk(int cost, int sanso, int x, int y, int h, int w) {
		super();
		this.cost = cost;
		this.sanso = sanso;
		this.x = x;
		this.y = y;
		visited = new boolean[h][w];
	}

	public Walk(Walk w) {
		this.cost = w.cost;
		this.sanso = w.sanso;
		this.x = w.x;
		this.y = w.y;
		visited = new boolean[w.visited.length][w.visited[0].length];
		for (int i = 0; i < w.visited.length; i++) {
			visited[i] = Arrays.copyOf(w.visited[i], w.visited[0].length);
		}
	}

	@Override
	public int compareTo(Walk arg0) {
		return this.cost - arg0.cost;
	}
}

Measured memory_bytes: 73868
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
// #define INF __INT32_MAX__
#define INF 1e9
#define LINF __LONG_LONG_MAX__

int main() {
    string S; cin >> S;
    int l = S.size();

    ll res = 0;
    for (int i = 0; i < 1<<(l - 1); i++) {
        vector<char> x;
        for (int j = 0; j < (l - 1); j++) {
            x.push_back(S.at(j));
            if (i & 1<<j) {
                x.push_back('+');
            }
        }
        x.push_back(S.at(l - 1));

        vl y;
        string tmp;
        rep(i, x.size()) {
            if (x[i] == '+') {
                y.push_back(stol(tmp));
                tmp = "";
            } else {
                tmp += x[i];
            }
        }
        if (tmp != "") y.push_back(stol(tmp));

        rep(i, y.size()) res += y[i];
    }
    cout << res << endl;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif

int main() {
   Int a, b, c, x;
   std::cin >> a >> b >> c >> x;
   Int xs[3] = {500, 100, 50};
   Int res = 0;
   for(Int i = 0; i <= a; ++i)
      for(Int j = 0; j <= b; ++j)
         for(Int k = 0; k <= c; ++k)
            if( xs[0] * i + xs[1] * j + xs[2] * k == x )
               res += 1;
   printf("%ld\n", res);
}


Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
        long long int n,c=0,j=0;
        cin>>n;
        long long int a[n+1];
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
        {
        

            if(i%2==1 && a[i]%2==1)
                c++;
        }
        cout<<c;
        
        
    }
    
    


Measured memory_bytes: 3636
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)

int main() {
  ll A, B;
  cin >> A >> B;
  ll ans = 0;
  if (A != 1 && B != 1) {
    ans = 1;
  }
  if (A != 2 && B != 2) {
    ans = 2;
  }
  if (A != 3 && B != 3) {
    ans = 3;
  }

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


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


void trace(int A[], int N){
    for (int i=0; i<N; i++){
        if(i>0){
            printf(" ");
        }
        printf("%d", A[i]);
    }
    printf("\n");
}

void insertionSort(int A[], int N){
    int j, i, v;
    for (i=1; i<N; i++){
        v = A[i];
        j = i - 1;
        while(j>=0 && A[j]>v){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        trace(A, N);
    }
}

int main(){
    int N;
    int A[100];
    
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        scanf("%d", &A[i]);
    }
    
    trace(A, N);
    insertionSort(A, N);
    return 0;
}


Measured memory_bytes: 3196
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30;
int MOD = 1e9+7;
main(){
    int X;
    cin >> X;
    ll maxi = 1;
    for(int i = 2;i*i <= X;i++){
        ll j = i;
        while(j <= X){
            j *= i;
        }
        maxi = max(maxi, j/i);
    }
    cout << maxi << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[]) {
  // read inputs
  long W, H, x, y;
  scanf("%ld %ld %ld %ld", &W, &H, &x, &y);

  // solve
  printf("%lf", W * H / 2.0);
  if (2 * x == W && 2 * y == H) {
    printf(" 1\n");
  } else {
    printf(" 0\n");
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 998244353
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 200003
#define pc(x) putchar_unlocked(x);

int dep[1003][5005],n,p[1003],x[mx];
vector<int>g[1003];

int dp(int now,int ke,int tot){
	if(ke==g[now].size())return 0;
	int&ret=dep[g[now][ke]][tot];
	if(ret!=-1)return ret;
	ret=1e9;
	if(x[g[now][ke]]+tot<=x[now])ret=min(ret,dp(now,ke+1,tot+x[g[now][ke]])+dp(g[now][ke],0,0));
	if(dp(g[now][ke],0,0)+tot<=x[now])ret=min(ret,dp(now,ke+1,tot+dp(g[now][ke],0,0))+x[g[now][ke]]);
	return ret;
}

int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>p[i];
		g[p[i]].pb(i);
	}
	for(int i=1;i<=n;i++)cin>>x[i];
	reset(dep,-1);
	if(dp(1,0,0)==1e9)cout<<"IMPOSSIBLE\n";
	else cout<<"POSSIBLE\n";
	
}




Measured memory_bytes: 19968
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<=n;++i)
int main(){
  int n;cin>>n;
  int orin=n;
  int ans[100];
  int s=0;
  while(n!=0){
    if(n%2==0)ans[s]=0;
    else{
    ans[s]=1;
    if(1)n--;
    else n++;
    }
    s++;
    n/=-2;
    //    cout<<n<<endl;
  }
  if(orin==0){
    s=1;
    ans[0]-0;
  }
  for(int i=1;i<=s;i++){
    cout<<ans[s-i];
  }
  cout<<endl;
  //  cout<<-90%2<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
#define rg register
#define inf 0x3f3f3f3f
#define MX 100050
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int n,j,k;
int a[MX],b[MX],c[MX];
ll ans;
int main(){
    // freopen("a.in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=n;i++) c[i]=read();

    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);
    for(int i=1;i<=n;i++)
    {
        while(a[j+1]<b[i]&&j+1<=n) j++;
        while(c[k+1]<=b[i]&&k+1<=n) k++;
        ans+=1LL*j*(n-k);
    }
    printf("%lld\n",ans);
    return 0;
}

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

int main(){
  string a,b;
  cin >> a >> b;
  bool ans = true ;
  if(a=="D"){
    ans = !ans;
  }
  if(b=="D"){
    ans = !ans;
  }
  if(ans == true){
    cout << "H" << endl;
  } else {
    cout << "D" << endl;
  }
}


Measured memory_bytes: 256
N = int(input())
H = [int(h) for h in input().split()]

dp = [0]*N
dp[1] = abs(H[1]-H[0])
for i in range(2, N):
    dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]), dp[i-2]+abs(H[i]-H[i-2]))
    
print(dp[N-1])

Measured memory_bytes: 13928
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<pair<ll,ll> > adj[100005];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string str;
    cin>>str;
    if(str=="ABC")
        cout<<"ARC"<<endl;
    else
        cout<<"ABC"<<endl;
    return 0;
}


Measured memory_bytes: 5956
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		if (sc.nextInt() +  sc.nextInt() + sc.nextInt() > 21) {
			System.out.println("bust");
		}else {
			System.out.println("win");
		}
	}
}

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

using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
#define REP(i, n) for(int i=1;i<=n;i++)
typedef long long ll;

int main() {
	ll a, b, k;
	cin >> a >> b >> k;
	if (a + k - 1>= b - k + 1) {
		for (int i = a; i <= b; ++i) {
			cout << i << endl;
		}
	} else {
		rep(i, k) {
			cout << a + i << endl;
		}
		for (int i = b - k + 1; i <= b; ++i) {
			cout << i << endl;
		}
	}
	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 36

struct Data{
  int num;
  char moji[3];
};
  
int main(){
  int n,i,j,min,k;
  struct Data date[N],change,date2[N];

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",date[i].moji);
    date[i].num = atoi(&date[i].moji[1]);
    date2[i] = date[i];
  }

  for (i = 0; i < n - 1; i++) {
    for (j = n - 1; j > i; j--) {
      if ( date[j - 1].num > date[j].num ) {  
	change = date[j];
	date[j] = date[j-1];
	date[j-1] = change;
      }
    }
  }

   for (i = 0; i < n - 1; i++) {
        min = date2[i].num;                 
        k = i;                       
        for (j = i + 1; j < n; j++) {
            if (date2[j].num < min) {       
                min = date2[j].num;        
                k = j;               
            }
        }                            
	change = date2[i];
	date2[i] = date2[k];
	date2[k] = change;
   }


  for(i=0;i<n-1;i++){
    printf("%s ",date[i].moji);
  }
  printf("%s\nStable\n",date[i].moji);

  k = 0;
  for(i=0;i<n-1;i++){
    if( strcmp( date[i].moji,date2[i].moji ) != 0 ) k = 1;
    printf("%s ",date2[i].moji);
  }
  if( strcmp( date[n-1].moji,date2[n-1].moji ) != 0 ) k = 1;
  if( k == 0 ) printf("%s\nStable\n",date2[i].moji);
  else printf("%s\nNot stable\n",date2[i].moji);
  return 0;
}

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

struct seg_t {
	const int n;
	vector<int> seg;
	seg_t(int n): n(n), seg(n + n) {}
	void add(int i) {
		for (seg[i += n]++; i /= 2;)
			seg[i] = seg[i + i] + seg[i + i + 1];
	}
	int query(int l, int r) {
		int ql = 0, qr = 0;
		for (l += n, r += n; l < r; l /= 2, r /= 2) {
			if (l & 1) ql = ql + seg[l++];
			if (r & 1) qr = seg[--r] + qr;
		}
		return ql + qr;
	}
};

const int mod = 1e9 + 7;

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	vector<int> s = a;
	std::sort(s.begin(), s.end());
	vector<int> order = s;
	auto new_end = std::unique(order.begin(), order.end());
	order.erase(new_end, order.end());
	auto idx = [&](int v) -> int {
		auto it = std::lower_bound(order.begin(), order.end(), v);
		return it - order.begin();
	};
	seg_t seg(order.size());
	int ans = 0, c2 = (1ll * k * (k - 1) / 2) % mod;
	for (int i = 0; i < n; i++) {
		int where = idx(a[i]);
		int s2 = seg.query(where + 1, order.size());
		seg.add(where);
		int x = s.end() - std::upper_bound(s.begin(), s.end(), a[i]);
		ans = (ans + 1ll * k * s2) % mod;
		ans = (ans + 1ll * c2 * x) % mod;
	}
	std::cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
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();

        boolean isKawaisou = false;
        if (a == b && a != c) {
            isKawaisou = true;
        }
        if (a == c && a != b) {
            isKawaisou = true;
        }
        if (b == c && a != b) {
            isKawaisou = true;
        }

        if (isKawaisou) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }

}

Measured memory_bytes: 35836
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int, int> p;
 
int main() {
	cin.tie(0);
    ios::sync_with_stdio(false);

    ll mod = pow(10, 9) + 7;

    vector<ll> x(1000);

    ll N;
    cin >> N;

    ll ans = 1;

    for(ll i = 2LL; i <= N; i++) {
        ll n = i;

        for(ll j = 2; j * j <= n; j++) {
            while(n % j == 0) {
                x[j]++;
                n /= j;
            }
        } 

        if(n != 1) x[n]++;
    }

    for(int i = 0; i < 1000; i++) {
        ans *= x[i] + 1LL;
        ans %= mod;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
#define anD &&
#define oR ||
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define rep(i,n) for((i)=0;(i)<(n);(i)++)

int main(void) {
	int n, i, tmp,b;
	int min, idx, max = -214;
	scanf("%d", &n);
	scanf("%d", &tmp);
	min = idx = tmp;
	for (i = 1; i < n; i++) {
		scanf("%d",&tmp);
		idx = tmp;
		b = idx - min;
		if (tmp < min) min = tmp;

		if (n == 2 oR b > max) max = b;
	}
	printf("%d\n" , max);
	return 0;
}

Measured memory_bytes: 596
n,m=map(int,input().split())
shima=dict()
for i in range(m):
    a,b=map(int,input().split())
    if a not in shima:
        shima[a]=[b]
    else:
        x=shima[a]
        x.append(b)
        shima[a]=x

flag=False
start=0

if 1 in shima:
    for next_shima in shima[1]:
        if next_shima in shima:
            if n in shima[next_shima]:
                flag=True 


#print(shima)

if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 30704
// D - Banned K
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(n);++i)

ll nC2(ll n){return n*(n-1)/2;}//組み合わせ

int A[200000], C[200000];

int main(){
	int N; cin>>N;
	rep(i, N){ scanf("%d",A+i); A[i]--; C[A[i]]++; }//値の種類毎の計数
	ll all = 0; rep(a, N) all += nC2(C[a]);//組み合わせの総計
	rep(k, N) printf("%lld\n",all - nC2(C[A[k]]) + nC2(C[A[k]]-1));
}

Measured memory_bytes: 3712
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc 030 A
"""

a, b, c = map(int, input().split())

if c <= a+b:
    ans = b+c
if c > a+b:
    ans = a+b+b+1

print (ans)


Measured memory_bytes: 2940
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
static int[] segttt = new int[(1<<18)];
static int segkkk = 0;
static int seglll = 0;
static int segrrr = (1<<17);
static int[] segValue = new int[100005];

static void Main()
{    
  string[] input = Console.ReadLine().Split(' ');
	int n = int.Parse(input[0]);
	int q = int.Parse(input[1]);
  segValue[0] = 2147483647;//初期化
  for(int i = 1; i <= q; i++)
  {
    int[] inputa = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
    if(inputa[0] == 0)
    {
      segValue[i] = inputa[3];
      AreaChangePointGetSeg(inputa[1], inputa[2], i);
    }else
    {
      int answer = AreaChangePointGetSegAnswer(inputa[1]);
      Console.WriteLine(segValue[answer]);
    }
  }
}

static void AreaChangePointGetSeg(int a, int b, int x)
{
  AreaChangePointGetSegSub(a,b+1,x,segkkk,seglll,segrrr);
}
  
static void AreaChangePointGetSegSub(int a, int b, int x, int segkkk, int seglll, int segrrr)
{//区間以上以下の値を全てchangeNumに変更し、ある１点の値を求める。入力側
  if(b <= seglll || segrrr <= a)
  {
    b = b;
  }
  else if(a <= seglll && segrrr <= b)
  {
    segttt[segkkk] = Math.Max(segttt[segkkk],x);
  }else
  {
    int m = (seglll+segrrr)/2;
    AreaChangePointGetSegSub(a, b, x, segkkk*2+1, seglll, m);
    AreaChangePointGetSegSub(a, b, x, segkkk*2+2, m, segrrr);
  }
}
  
static int AreaChangePointGetSegAnswer(int i)
{//区間以上以下の値を全てchangeNumに変更し、ある１点の値を求める。出力側。
  i += (1<<17)-1;
  int res = segttt[i];
  while(i != 0)
  {
    i = (i-1)/2;
    res = Math.Max(res,segttt[i]);
  }
  return res;
}

}


Measured memory_bytes: 22560
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = (long long)1000000; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}

#define MAX 110

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N, M;
	
	cin>>N>>M;
	
	
	if(M == 1){
		int ans = 1;
		
		for(int i = 0; i < N; i++){
			ans *= 2;
			ans %= MOD;
		}
		cout<<ans<<endl;
	} else {
		int ans = 1;
		static int dp[MAX][4] = {}, dp2[MAX][4] = {};
		
		dp[0][1] = 1;
		
		for(int i = 1; i <= N+1; i++){
			for(int j = 1; j <= 3; j++){
				dp[i][j] = dp[i-1][j] + dp[i][j-1];
				dp[i][j] %= MOD;
			}
			dp[i][1] += dp[i-1][2] + dp[i-1][3];
			
			dp[i][2] += dp[i-1][3];
			
			int c1[MAX] = {}, c2[MAX] = {};
			int t1, t2;
			
			for(int j = 0; j < i; j++){
				for(int k = j+1; k < i; k++){
					dp[i][3] += MOD + dp[j][1] - c1[k];
					c1[k] += MOD + dp[j][1] - c1[k];
					dp[i][3] %= MOD;
					c1[k] %= MOD;
					
					dp[i][1] += MOD + dp[j][3] - c2[k];
					c2[k] += MOD + dp[j][3] - c2[k];
					dp[i][1] %= MOD;
					c2[k] %= MOD;
				}
			}
			
			dp[i][2] %= MOD;
		}
		
		cout<<dp[N+1][3]%MOD<<endl;
	}
	
	return 0;
}


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

int main() {
  int t;
  cin >> t;
  vector<int> v(t);
  
  for (int i = 0; i < t; ++i)
    cin >> v[i];
  
  int dp[t+1];
  dp[0] = 0;
  dp[1] = abs(v[1] - v[0]);
  
  for (int i = 2; i < t; ++i)
    	dp[i] = min(dp[i-1] + abs(v[i] - v[i-1]), dp[i-2] + abs(v[i-2] - v[i]));
  
  cout << dp[t - 1] << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)

int main()
{
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    rep(i, b) {
        cout << a;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    int n;
    while(cin >> n, n){
        vp v;
        rep(i,n){
            int t;
            cin >> t;
            if(v.size()){
                if(v.back().first == t){
                    v.back().second++;
                }else if(i%2 == 0){
                    v.push_back(pii(t,1));
                }else{
                    int tmp = v.back().second + 1;
                    v.pop_back();
                    if(v.size())v.back().second += tmp;
                    else v.push_back(pii(t,tmp));
                }
            }else{
                v.push_back(pii(t,1));
            }
            //cout << "!"<<i << endl;
            //rep(j,v.size())cout << v[j].first << " " << v[j].second << endl;
        }
        int ans = 0;
        rep(i,v.size())if(!v[i].first)ans += v[i].second;
        cout << ans << endl;
    }
}



Measured memory_bytes: 2996
//https://atcoder.jp/contests/abc128/tasks/abc128_c
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
const ll LINF = 0x1fffffffffffffff;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
#if LOCAL&01
  std::ifstream in("./test/sample-1.in");
  //std::ifstream in("./input.txt");
  std::cin.rdbuf(in.rdbuf());
#else
  cin.tie(0);
  ios::sync_with_stdio(false);
#endif
  ll N,M; cin>>N>>M;
  vector<ll> smm(M);
  vector<ll> pm(M);

  FOR(i,0,M){
    ll k; cin>>k;
    ll msk=0;
    REP(j,k){
      ll s; cin>>s; --s;
      msk |= 1<<s;
      smm.at(i)=msk;
    }
  }
  for(auto&& p:pm){
    cin>>p;
  }

  ll ans=0;
  ll bit_max=1<<N;
  FOR(b,0,bit_max){
    bool flag=true;
    FOR(i,0,M){
      ll msk = b&smm.at(i);
      ll n = __builtin_popcount(msk) % 2;
      if(pm.at(i)!=n) {
        flag=false;
        break;
      }
    }
    if(flag)++ans;
  }
  cout<<ans<<endl;
  return 0;
}

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

int main() {
  int N, c;
  c = 0;
  cin >> N;
  vector<int> p(N);
  for (int i = 0; i < N; i++){
    cin >> p.at(i);
  }
  for (int i = 0; i < N; i++){
    if (p.at(i) != i+1){
      c++;
    }
  }
  if (c == 2 || c == 0){
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main()
{
int n;
int k;
cin>>n>>k;
set<int>Q;
int d,e;

for(int i=0;i<k;i++)
{
cin>>d;
for(int j=0;j<d;j++)
{cin>>e;Q.insert(e);}
}


cout <<n-Q.size();

}

Measured memory_bytes: 3636
//   __                    .__              ________ .________ ________   ______  
//  |  | __  ____    ______|  |__   __ __  /  _____/ |   ____//   __   \ /  __  \ 
//  |  |/ /_/ __ \  /  ___/|  |  \ |  |  \/   __  \  |____  \ \____    / >      < 
//  |    < \  ___/  \___ \ |   Y  \|  |  /\  |__\  \ /       \   /    / /   --   \
//  |__|_ \ \___  >/____  >|___|  /|____/  \_____  //______  /  /____/  \______  /
//       \/     \/      \/      \/               \/        \/                  \/ 

#include<bits/stdc++.h>
#define range 100005
#define mod 1000000007
#define eps 1e-9
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define _ <<" "<<
#define int long long 

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair <int, int> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<ii> vii;
typedef vector<iii> viii;

vi graph[200000];

int output = 1;
int n,k;

void dfs(int v,int p=-1){
	int temp = k-1;
	int tempo = k-2;
	for(int u:graph[v]){
		if(u!=p){
			if(p==-1){
				dfs(u,v);
				output*=temp;
				output%=mod;
				temp--;
			}
			else{
				dfs(u,v);
				output*=tempo;
				output%=mod;
				tempo--;
			}
		}
	}
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("test.txt","r",stdin);
	cin>>n>>k;
	for(int i=0;i+1<n;i++){
		int u,v;
		cin>>u>>v;
		graph[u].pb(v);
		graph[v].pb(u);
	}
	output = k;
	dfs(1);
	cout<<output;
	return 0;
}


Measured memory_bytes: 13952
K,N=map(int, input().split())
As=list(map(int, input().split()))
ans=K
m=0
for i in range(len(As)-1):
    if As[i+1]-As[i] > m:
        m=As[i+1]-As[i]
if As[0]+K-As[-1]>m:
    m=As[0]+K-As[-1]
print(ans-m)

Measured memory_bytes: 25840
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

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

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

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  vector<lint> digit(1000010,0);
  string n;
  cin>>n;
  for(int i=0;i<n.size();i++){
    digit[n.size()-1-i]=n[i]-'0';
  }
  vector<lint> pay,back;

  lint result=0;
  for(int i=0;i<n.size()+1;i++){
    if(digit[i]>=6){
      digit[i+1]++;
      result+=10-digit[i];
      pay.push_back(0);
      back.push_back(10-digit[i]);
    }else if(digit[i]==5){
      if(digit[i+1]<=4){
        result+=5;
        pay.push_back(5);
        back.push_back(0);
      }else{
        digit[i+1]++;
        result+=5;
        pay.push_back(0);
        back.push_back(5);
      }
    }else{
      result+=digit[i];
      pay.push_back(digit[i]);
      back.push_back(0);
    }
  }
  // for(int i=pay.size()-1;i>=0;i--){
  //   cerr<<pay[i];
  // }
  // cerr<<endl;
  // for(int i=back.size()-1;i>=0;i--){
  //   cerr<<back[i];
  // }
  // cerr<<endl;

  cout<<result<<endl;

  return 0;
}




Measured memory_bytes: 26372