akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever while (true)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vd = std::vector<double>;
using vc = std::vector<char>;
using vb = std::vector<bool>;
using vs = std::vector<std::string>;
using vpii = std::vector<pii>;
using vvi = std::vector<vi>;
using vvb = std::vector<vb>;
using vvpii = std::vector<vpii>;
template<typename A> using fn = std::function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
using namespace std;

template<typename MonoidTrait> class SegTree {
  using Monoid = MonoidTrait;
  using T = typename Monoid::value_type;

  Monoid m;
  std::vector<T> data;
  int size = 1;

public:
  SegTree(const int &n = 0) {
    m = Monoid();
    while (size < n) size *= 2;
    data.assign(size * 2, m.id());
  }

  template<typename InputIterator> SegTree(InputIterator first, InputIterator last) {
    m = Monoid();
    int n = std::distance(first, last);
    while (size < n) size *= 2;
    data.resize(size * 2, m.id());
    std::copy(first, last, data.begin() + size);
    for (int i = size - 1; i >= 1; --i) data[i] = m(data[i * 2 + 0], data[i * 2 + 1]);
  }

  T fold(int l, int r) const { // TODO [l, r)
    T acc = m.id();
    for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
      if (l & 1) acc = m(acc, data[l++]);
      if (r & 1) acc = m(acc, data[--r]);
    }
    return acc;
  }

  void update(int i, const T &x) { // TODO
    data[i += size] = x;
    while (i > 1) {
      data[i / 2] = m(data[i], data[i ^ 1]);
      i /= 2;
    }
  }

  const T &operator[](int i) const { return data[i + size]; }
};

template<typename T, T upperInf = std::numeric_limits<T>::max()> struct minMonoid {
  using value_type = T;
  constexpr T id() const { return upperInf; }
  T operator()(const T &a, const T &b) const { return std::min(a, b); }
};

main {
  using RMQ = SegTree<minMonoid<int, 2147483647>>;
  int n, q;
  cin >> n >> q;
  RMQ t(n);
  while (q--) {
    int com, x, y;
    cin >> com >> x >> y;
    if (com) {
      cout << t.fold(x, y + 1) << endl;
    } else {
      t.update(x, y);
    }
  }
}

Measured memory_bytes: 4940
n,m=[int(i) for i in input().split()]
h=[[int(i),[]] for i in input().split()]

for i in range(m):
    a,b=[int(i) for i in input().split()]
    a-=1
    b-=1
    h[a][1].append(b)
    h[b][1].append(a)

r=0
for i in range(len(h)):
    for j in range(len(h[i][1])):
        if h[i][0] <= h[h[i][1][j]][0]:
            break
    else:
        r+=1

print(r)


Measured memory_bytes: 37364
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    dp = [[0]*W for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
            if C[h][w].isdigit():
                dp[h][w] = max(dp[h][w],int(C[h][w]))
                if w > 0: dp[h][w] = max(dp[h][w],int(str(dp[h][w-1])+C[h][w]))
                if h > 0: dp[h][w] = max(dp[h][w],int(str(dp[h-1][w])+C[h][w]))
    print max(max(i) for i in dp)

Measured memory_bytes: 4316
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <iomanip>
using namespace std;
int main(){
	int n,m;
	string s;
	cin>>n>>m>>s;
	long long dp[100001];
	int mae[100001];
	fill(dp,dp+n+1,1e9+7);
	dp[0]=0;
	for(int i=1;i<=m;i++){
		if(s[i]=='0'){
			dp[i]=1;
			mae[i]=0;
		}
	}
	for(int i=m+1;i<=n;i++){
		if(s[i]=='1'){
			continue;
		}
		bool f=1;
		for(int j=i-m;j<i;j++){
			if(s[j]=='0'){
				dp[i]=dp[j]+1;
				mae[i]=j;
				f=0;
				break;
			}
		}
		if(f){
			cout<<-1<<endl;
			return 0;
		}
	}
	int now=n;
	vector<int> ans;
	ans.push_back(now);
	ans.push_back(mae[now]);
	while(mae[now]){
		now=mae[now];
		ans.push_back(mae[now]);
	}
	reverse(ans.begin(),ans.end());
	vector<int> sna;
	for(int i=1;i<ans.size();i++){
		sna.push_back(abs(ans[i]-ans[i-1]));
	}
	for(int i=0;i<sna.size();i++){
		cout<<sna[i];
		if(i==sna.size()-1){
			cout<<endl;
		}else{
			cout<<" ";
		}
	}
	return 0;
}


Measured memory_bytes: 2744
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    a = [input() for _ in range(h)]
    for i,ai in enumerate(a):
        if "S" in ai:
            si = i
            sj = ai.find("S")
            break
    q = queue.Queue()
    t = [[10**10]*w for _ in [0]*h]
    dir = [(-1,0),(1,0),(0,-1),(0,1)]
    t[si][sj] = 0
    q.put((si,sj))
    g1 = [(si,sj)]
    while not q.empty():
        qi,qj = q.get()
        for di,dj in dir:
            if 0 <= qi+di <= h-1 and 0 <= qj+dj <= w-1 and a[qi+di][qj+dj] == ".":
                if t[qi+di][qj+dj] > t[qi][qj] + 1:
                    t[qi+di][qj+dj] = t[qi][qj] + 1
                    g1.append((qi+di,qj+dj))
                    if t[qi][qj] != k-1:
                        q.put((qi+di,qj+dj))

    mi = 10**4
    for i,j in g1:
        if mi > (i+k-1)//k+1:
            mi = (i+k-1)//k+1
        if mi > (j+k-1)//k+1:
            mi = (j+k-1)//k+1
        if mi > (h-1-i+k-1)//k+1:
            mi = (h-1-i+k-1)//k+1
        if mi > (w-1-j+k-1)//k+1:
            mi = (w-1-j+k-1)//k+1
    print(mi)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 115072
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
const int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

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

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

void solve() {
  int m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;
  if (m1 != m2) cout << 1 << endl;
  else cout << 0 << endl;
}


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

typedef struct shiranui {
    ll id, a, b;
    shiranui(ll _id, ll _a, ll _b) : id(_id), a(_a), b(_b) {}
} flare;

const ll inf = 1e18;
const ll upper = 2500;

int main() {
    ll n, m, s;
    cin >> n >> m >> s;
    vector<vector<ll>> dist(n, vector<ll>(upper+10, inf));
    vector<vector<flare>> G(n);
    rep(i, 0, m) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        G[u].push_back(flare(v, a, b));
        G[v].push_back(flare(u, a, b));
    }
    vector<ll> c(n), d(n);
    rep(i, 0, n) cin >> c[i] >> d[i];
    typedef pair<ll,ll> pl;
    typedef pair<ll, pl> tl;
    priority_queue<tl, vector<tl>, greater<tl>> que;
    que.push({0, {0, min(s, upper)}});
    dist[0][min(s, upper)] = 0;
    while(!que.empty()) {
        auto q = que.top();
        que.pop();
        auto time = q.first;
        auto cur = q.second.first;
        auto coin = q.second.second;
        if(time > dist[cur][coin]) continue;
        // 移動
        for(auto g : G[cur]) {
            if(coin - g.a < 0) continue;
            if(dist[g.id][coin-g.a] <= time + g.b) continue;
            dist[g.id][coin-g.a] = time + g.b;
            que.push({dist[g.id][coin-g.a], {g.id, coin-g.a}});
        }
        // 補充
        auto next = coin + c[cur];
        if(next > upper) next = upper;
        if(dist[cur][next] <= time + d[cur]) continue;
        dist[cur][next] = time + d[cur];
        que.push({dist[cur][next], {cur, next}});
    }
    rep(i, 1, n) {
        ll mn = inf;
        rep(j, 0, upper + 1) mn = min(mn, dist[i][j]);
        cout << mn << endl; 
    }
    return 0;
}

Measured memory_bytes: 7256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Range(container) container.begin(), container.end()
#define RevRange(container) container.rbegin(), container.rend()
#define Cin(T, x) T x; cin >> x;
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i];
#define Cout(val) cout << (val) << "\n";
using namespace std;
using ll = long long;

int main(void){
    Cin(int, n);
    Cin(int, m);
    vector<int> a(m+1);
    
    For(i, n){
        Cin(int, k);
        For(j, k){
            Cin(int, v);
            a[v] ++;
        }
    }
    
    int ans = 0;
    For(i, m+1){
        if(a[i] == n) ans ++;
    }
    Cout(ans);
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1002;
char s[maxn];
int main()
{
	bool sth=0,nth=0,eth=0,wth=0;
	scanf("%s",s);
	int n=strlen(s);
	for(int i=0;i<n;++i)
		if(s[i]=='S')sth=1;
		else if(s[i]=='E')eth=1;
		else if(s[i]=='W')wth=1;
		else if(s[i]=='N')nth=1;
	if( (sth&&!nth) || (!sth&&nth) )puts("No");
	else if( (eth&&!wth) || (!eth&&wth) )puts("No");
	else puts("Yes");
	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
c = 0
for i in a:
  if i % 2 == 0:
    if i % 3 != 0 and i % 5 != 0:
      c += 1
if c == 0:
  print("APPROVED")
else:
  print("DENIED")

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

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

	ll a,b,c;
	cin>>a>>b>>c;

	ll d = c - a - b;

	if(d>0 && d*d > 4*a*b)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <regex>
#include <climits>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return b;
    }
    return gcd(b, a % b);
}

int main()
{
    string S;
    cin >> S;

    bool ok = true;
    for (ll i = 0; i < S.size(); i++)
    {
        if (i % 2 == 0) {
            ok &= S[i] == 'R' || S[i] == 'U' || S[i] == 'D';
        } else {
            ok &= S[i] == 'L' || S[i] == 'U' || S[i] == 'D';
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
}

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

using namespace std;
 
#define MD 1000000007
typedef long long int ll;

int main(){
    int h,w,cnt_b=0;
    cin>>h>>w;
    char v[51][51]={'\0'};
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>v[i][j];
            if(v[i][j]=='#'){
                cnt_b++;
            }
        }
    }
    
    queue<int> qy,qx;
    qy.push(0); qx.push(0);//初期位置をpush
    int x,y,dis[51][51]={0};//disは，現在いる点に最短でいくつの点を通ってきたか
    dis[0][0]=1; v[0][0]='#';
    while(qy.empty()!=1){//空じゃない限り回す
        y=qy.front(); x=qx.front();//値を取り出す
        qy.pop(); qx.pop();//値をポップ
        if(y-1>=0){
            if(v[y-1][x]=='.'){//上移動
            v[y-1][x]='#';
            qy.push(y-1); qx.push(x);
            dis[y-1][x]=dis[y][x]+1;
            }
        }
        if(y+1<h){
            if(v[y+1][x]=='.'){//下移動
            v[y+1][x]='#';
            qy.push(y+1); qx.push(x);
            dis[y+1][x]=dis[y][x]+1;
            }
        }
        if(x-1>=0){
            if(v[y][x-1]=='.'){//左移動
            v[y][x-1]='#';
            qy.push(y); qx.push(x-1);
            dis[y][x-1]=dis[y][x]+1;
            }
        }
        if(x+1<w){
            if(v[y][x+1]=='.'){//左移動
            v[y][x+1]='#';
            qy.push(y); qx.push(x+1);
            dis[y][x+1]=dis[y][x]+1;
            }
        }
    }
    
    if(dis[h-1][w-1]==0){
        cout<<-1<<endl;
    }else{
        int ans=h*w-dis[h-1][w-1]-cnt_b;
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){

    int n;
    cin >> n;

    int tmp, count;
    int ans = n;
    for(int i=0;i<=n;i++){
        count = 0;
        tmp = i;
        while(tmp>0){
            count += tmp % 9;
            tmp /= 9;
        }
        tmp = n - i;
        while(tmp>0){
            count += tmp % 6;
            tmp /= 6;
        }
        if(ans>count)ans = count;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    int[] b = new int[100010];

    for (int i = 0; i < N; i++) {
      int a = sc.nextInt();
      b[a]++;
    }

    sc.close();

    int max = 0;

    for (int i = 0; i < 100010-2; i++) {
      max = Math.max(max, b[i] + b[i+1] + b[i+2]);
    }

    System.out.println(max);

  }

}

Measured memory_bytes: 51600
n,*t=map(int,open(0).read().split())
x=sorted(zip(t[1:n*2:2],t[:n*2:2]))
y=sorted(zip(t[n*2::2],t[n*2+1::2]))[::-1]
c=0
while y:
  i,j=y.pop()
  k=len(x)-1
  while k>=0:
    b,a=x[k]
    if a<i and b<j:
      c+=1
      del x[k]
      break
    k-=1
print(c)

Measured memory_bytes: 3064
// #include {{{
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iterator>
#include <tuple>
#include <utility>
#include <random>
#include <limits>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <cassert>

#ifdef DEBUG
#include <fmt/format.h>
#endif
// }}}

using namespace std;

// macros {{{
template<typename T, size_t N>
constexpr size_t NELEMS(T (&)[N]) { return N; }

template<typename InputIt>
void PRINT_RANGE(InputIt first, InputIt last)
{
    for(; first != last; ++first)
        cout << *first << (first==last ? "" : " ");
    cout << "\n";
}

template<typename T>
void PRINT_MATRIX(T mat, size_t nr, size_t nc)
{
    for(size_t r = 0; r < nr; ++r) {
        for(size_t c = 0; c < nc; ++c) {
            cout << mat[r][c] << (c==nc-1 ? "" : " ");
        }
        cout << "\n";
    }
}

#define FOR(i, start, end) for(int i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)
// }}}

// types {{{
using s64 = int64_t;
using u64 = uint64_t;
// }}}

int N, M;
vector<vector<int>> G;

void lengthen(vector<int>& apath, deque<bool>& visited)
{
    for(;;) {
        bool done = true;
#ifdef DEBUG
        cout << apath.back() << "\n";
#endif
        for(int v : G[apath.back()]) {
            if(!visited[v]) {
                done = false;
                apath.push_back(v);
                visited[v] = true;
                break;
            }
        }

        if(done) {
            break;
        }
    }
}

void solve()
{
    vector<int> apath;
    deque<bool> visited(N+1, false);

    apath.push_back(1);
    apath.push_back(G[1][0]);
    visited[1] = true;
    visited[G[1][0]] = true;

    lengthen(apath, visited);
    reverse(begin(apath), end(apath));
    lengthen(apath, visited);

    cout << apath.size() << "\n";
    for(size_t i = 0; i < apath.size(); ++i) {
        cout << apath[i] << (i == apath.size()-1 ? "\n" : " ");
    }
}

int main()
{
    cin >> N >> M;
    G.resize(N+1);

    REP(_, M) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
#ifdef DEBUG
    cout << "[G]\n";
    FOR(i, 1, N+1) {
        cout << i << ": ";
        PRINT_RANGE(begin(G[i]), end(G[i]));
    }
    cout << "---\n";
#endif

    solve();

    return 0;
}


Measured memory_bytes: 6908
package main

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

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	return n
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Scan()
	b := sc.Text()

	switch b {
	case "A":
		fmt.Println("T")
	case "T":
		fmt.Println("A")
	case "C":
		fmt.Println("G")
	case "G":
		fmt.Println("C")
	}

}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<iomanip>
#include <math.h>
using namespace std;
int main(){
    string s,t;
    cin>>s>>t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end(),greater<>());
    if(t>s){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3584
S=input()
if "eraser" in S:
    S=S.replace("eraser","")
if "erase" in S:
    S=S.replace("erase","")
if "dreamer" in S:
    S=S.replace("dreamer","")
if "dream" in S:
    S=S.replace("dream","")
if len(S)==0:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3188
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
void read (int &x) {
    char ch = getchar(); x = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 2e5 + 10;
int n, k[N], l[N], r[N];
pair<int, int> p[N];
#define x first
#define y second
set<int> s;
vector<pair<int, int> > va, vb;
signed main() {
    int T; read (T);
    while (T--) {
        read (n); long long res = 0;
        va.clear(), vb.clear();
        for (int i = 1; i <= n; ++i) {
            read (k[i]), read (l[i]), read (r[i]);
            if (l[i] >= r[i])
                res += r[i], va.push_back (make_pair(l[i] - r[i], k[i]));
            else res += l[i], vb.push_back (make_pair(r[i] - l[i], n - k[i]));
        }
        s.clear(); sort (va.begin(), va.end());
        for (int i = 1; i <= va.size(); ++i) s.insert (i);
        set<int>::iterator it;
        for (int i = va.size() - 1; i >= 0; --i) {
            it = s.upper_bound (va[i].y);
            if (it == s.begin()) it = s.end(), --it, s.erase (it);
            else --it, s.erase (it), res += va[i].x;
        }
        s.clear(); sort (vb.begin(), vb.end());
        for (int i = 1; i <= vb.size(); ++i) s.insert (i);
        for (int i = vb.size() - 1; i >= 0; --i) {
            it = s.upper_bound (vb[i].y);
            if (it == s.begin()) it = s.end(), --it, s.erase (it);
            else --it, s.erase (it), res += vb[i].x;
        } printf ("%lld\n", res);
    }
    return 0;
}


Measured memory_bytes: 11892
import sys
input = sys.stdin.buffer.readline
N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])


Measured memory_bytes: 158704
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dbl;
#define sqr(int) (int * int)
#define sqr3(int) (int * int * int)
#define pi M_PI
#define nl "\n"



 
  int main(){
	ios::sync_with_stdio(true);
	cin.tie(0);
	int n,ac=0,wa=0,tle=0,re=0;
	cin >> n;
	string a;
	while(n--){
		cin >> a;
		if(a == "AC"){ac+=1;}
		if(a == "WA"){wa+=1;}
		if(a == "TLE"){tle+=1;}
		if(a == "RE"){re+=1;}
	}
	
	
	
	
	
	cout << "AC" << " " << "x" << " " << ac << endl;
    cout << "WA" << " " << "x" << " " << wa << endl;
    cout << "TLE" << " " << "x" << " " << tle << endl;
    cout << "RE" << " " << "x" << " " << re << endl;
}	
	
		
		
		
		
	

	



Measured memory_bytes: 3600
import java.util.*;
import java.math.*;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int x=sc.nextInt();
		for(int i=x; ;i++){
			int k=i;
			boolean ch=false;
			for(int j=2; j<k; j++){
				if(k%j==0){
					ch=true;
					break;
				}
			}
			if(!ch){
				System.out.println(i);
				break;
			}
		}
	}
}


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

using i64 = int64_t;

#define rep(i, x, y) for (i64 i = i64(x), i##_max_for_repmacro = i64(y); i < i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf = 1.01e9;
const i64 inf64 = 4.01e18;
const double eps = 1e-9;

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

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

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

template<typename T, size_t size> void fill(T (&ary)[size], const T& val){
    fill_n((T*)ary, size, val);
}

void solve() {
    //const i64 mod = 1'000'000'007;
    i64 A,P;
    cin >> A >> P;
    cout << (A*3+P)/2 << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  string s, t;
  cin >> s >> t;
  int n = s.length();
  if(n != t.length() - 1){
    cout << "No\n";
    return 0;
  }
  for(int i = 0; i < n; i++) {
    if(s[i] == t[i]){
      continue;
    }else{
      cout << "No\n";
      return 0;
    }
  }
  cout << "Yes\n";
  return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=924844033;
ll xlh,n,k,ii,i,j,st,op,la,a[2010],jc[2010],f[2010][2010][4],b[2010],g[2010],ans;
int main(){
	scanf("%lld%lld",&n,&k);
	jc[0]=1;
	for(i=1;i<=n;i++)jc[i]=jc[i-1]*i%p,a[i%k]++;
	g[0]=1;
	for(ii=0;ii<k;ii++){
		f[1][0][0]=1;
		if(a[ii]>1)f[1][1][2]=1;
		for(i=2;i<=a[ii];i++){
			for(j=0;j<=i;j++)
			 for(op=0;op<4;op++)f[i][j][op]=0;
			for(j=0;j<i;j++){
				for(op=0;op<4;op++){
				//	printf("%lld %lld %lld %lld\n",i,j,op,f[i-1][j][op]);
					f[i][j][op/2]=(f[i][j][op/2]+f[i-1][j][op])%p;
					if(op%2==0){
						f[i][j+1][op/2]=(f[i][j+1][op/2]+f[i-1][j][op])%p;
					}
					if(i<a[ii])f[i][j+1][op/2+2]=(f[i][j+1][op/2+2]+f[i-1][j][op])%p;
				}
			}
		}
		for(j=0;j<=a[ii];j++)
		 for(op=0;op<4;op++)
		 // printf("%lld %lld %lld %lld\n",a[ii]+1,j,op,f[a[ii]][j][op]);
		for(la=0;la<=n;la++)b[la]=0;
		for(la=0;la<=n;la++)
		for(j=0;j<=a[ii];j++)if(la+j<=n)
		 b[la+j]=(b[la+j]+g[la]*(f[a[ii]][j][0]+f[a[ii]][j][1]))%p;
		for(i=0;i<=n;i++){
			//printf("%lld ",g[i]);
		 g[i]=b[i];
	  }
	    // puts("");
	}
	for(i=0;i<=n;i++){
		xlh=g[i]*jc[n-i]%p;
		//printf("%lld %lld %lld\n",i,g[i],xlh);
		if(i%2)ans=(ans-xlh+p)%p;
		 else ans=(ans+xlh)%p;
	}
	printf("%lld",ans);
}

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

long long n;
long long a[500] = {0};
long long dp[500][500] = {0};

long long solve();

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i) cin >> a[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  for(int i = 1; i < n; ++i) a[i] += a[i - 1];
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      if(i != j) dp[i][j] = 10000000000000;
  for(int i = 1; i < n; ++i)
    for(int j = 0; i + j < n; ++j)
      for(int k = 0; k < i; ++k) {
        long long now =
            a[j + i] + dp[j][j + k] + dp[j + k + 1][j + i];
        if(j != 0) now -= a[j - 1];
        // dp[j][j+i]
        dp[j][j + i] = min(dp[j][j + i], now);
      }
  return dp[0][n - 1];
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define For(i,x,y) for(int i = x; i <= y; ++i)
#define FOR For
#define rev_For(i,x,y) for(int i = x; i >= y; --i)
#define REV_FOR rev_For
#define ll long long
#define Size(v) ((int)v.size())
#define _section "\n--------------------\n"
#define fi first
#define se second
#define pb push_back
using namespace std;
// using namespace __gnu_pbds;


int n, k;
const int nax = 1e5 + 5;
int h[nax];
int dp[nax];
const int INF = 1e9;

void input() {
	cin >> n >> k;
	FOR (i, 1 ,n) cin >> h[i];
	FOR (i, 0, nax - 1) dp[i] = -1;
	dp[1] = 0;
}

int calc(int i) {
	if (dp[i] != -1) return dp[i];
	if (i <= 0) return INF;

	int ret = INF;
	for (int j = i - 1; j >= i - k; --j) {
		if (j > 0) ret = min(ret, calc(j) + abs(h[i] - h[j]));
	}

	return (dp[i] = ret);
}

void solve() {
	cout << calc(n);
}

signed main() {
#ifdef _DEBUG
	// freopen("INPUT.inp", "r", stdin);
	//freopen("OUTPUT.out", "w", stdout);
	clock_t start, end;
	start = clock();
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//------------------------------------------------------------------------------------
//----------------------------------MAIN PROGRAM--------------------------------------
	int t = 1;
	while (t--) {
		input();
		solve();
	}
//--------------------------------------END-------------------------------------------
//------------------------------------------------------------------------------------
#ifdef _DEBUG
	end = clock();
	cerr << "\n----------\nTime Elapsed: " << fixed << double(end - start) / double(CLOCKS_PER_SEC) << setprecision(6) << '\n';
#endif
	return 0;
}

Measured memory_bytes: 5760
import fnmatch
S=[]
S.append(input())
if S == fnmatch.filter(S, "k*eyence") or S == fnmatch.filter(S, "ke*yence") or S == fnmatch.filter(S, "key*ence") or S == fnmatch.filter(S, "keye*nce") or S == fnmatch.filter(S, "keyen*ce") or S == fnmatch.filter(S, "keyenc*e") :
  print("YES")
else:
  print("NO")

Measured memory_bytes: 3828
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
	unsigned short *A,*B;
	int C[VMAX+1];
	int n,j,i;
	scanf("%d",&n);
	
	A=malloc(sizeof(short)*n+1);
	B=malloc(sizeof(short)*n+1);
	
	/* your code */
	for(i=0;i<=VMAX;i++){
		C[i]=0;
	}
	
	/* C[i] に i の出現数を記録する */
	for(i=0;i<n;i++){
		scanf("%hu",&A[i+1]);
		C[A[i+1]]++;
	}
	
	/* C[i] に i 以下の数の出現数を記録する*/
	for(i=1;i<=VMAX;i++){
		C[i]=C[i]+C[i-1];
	}
	
	for(j=1;j<=n;j++){
		B[C[A[j]]]=A[j];
		C[A[j]]--;
	}
	
	for(i=1;i<=n;i++){
		if(i>1)printf(" ");
		printf("%d",B[i]);
	}
	
	printf("\n");
	return 0;
}



Measured memory_bytes: 9636
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007; // 998244353;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const ld PI = acos((ld)-1);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

template <typename T> V<T> prefix_sum(const V<T>& v) {
  int n = v.size();
  V<T> ret(n + 1);
  rep(i, 0, n) ret[i + 1] = ret[i] + v[i];
  return ret;
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(auto&& x: vec) is >> x;
  return is;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
  return os<<"{"<<p.fs<<","<<p.sc<<"}";
}

template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
  os<<"{";
  for(auto e:v)os<<e<<",";
  return os<<"}";
}

template<typename ...Args>
void debug(Args&... args){
  for(auto const& x:{args...}){
    cerr<<x<<' ';
  }
  cerr<<ENDL;
}

template <typename T> struct UnionFind {
  vector<T> Parent;

  UnionFind(T N) { Parent = vector<T>(N, -1); }

  T root(T A) {
    if(Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }

  T size(T A) { return -Parent[root(A)]; }

  bool connect(T A, T B) {
    A = root(A);
    B = root(B);
    if(A == B) return false;
    if(size(A) < size(B)) swap(A, B);
    Parent[A] += Parent[B];
    Parent[B] = A;

    return true;
  }

  bool same(T A, T B) { return root(A) == root(B); }
};

signed main(){
  cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n,m;cin>>n>>m;
  UnionFind<ll> u(n);

  rep(i,0,m){
    int a,b;cin>>a>>b;
    --a;--b;
    u.connect(a,b);
  }

  set<int> se;
  rep(i,0,n){
    se.insert(u.root(i));
  }

  cout<<siz(se)-1<<ENDL;


}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 7916
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int n,a[100000],mina,maxa,cnt=0;
    scanf("%d",&n);
    mina=n;
    maxa=0;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        mina=min(mina,a[i]);
        maxa=max(maxa,a[i]);
    }
    if(mina+1<maxa){
        printf("No\n");
        return 0;
    }
    for(int i=0;i<n;i++){
        if(a[i]==mina&&mina!=maxa){
            cnt++;
        }
    }
    if(mina==maxa&&(mina==n-1||n>=mina*2)){
        printf("Yes\n");
        return 0;
    }
    if(cnt>=maxa||n-cnt<2*(maxa-cnt)){
        printf("No\n");
        return 0;
    }
    printf("Yes\n");
}

Measured memory_bytes: 512
import java.util.*;
import java.io.*;

public class Main {
	private static void solve(){
	//Implement solution here.
		int[] abc = na(3);
		Arrays.sort(abc);
		System.out.println(abc[0] * abc[1]/2);		
	}

    //Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
        String debugDataPath = System.getenv("DD_PATH");        
        if(debugDataPath != null){
            try{
            	br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
            }catch(Exception e){
                throw new RuntimeException(e);
            }
        }
        solve();
	}

    //Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
    //Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
    //Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
    //Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
    //Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
    //Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}


Measured memory_bytes: 21716
//inlclude前用define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
#include<type_traits>
#include<numeric>
#include<limits>
#include<iomanip>
using namespace std;
//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;

//grobal変数


int main() {
	int n, k;
	int sum = 0;
	cin >> n >> k;
	VI x(n);
	for (int i = 0; i < n; i++)cin >> x[i];

	for (int i = 0; i < n; i++) {
		sum += min(k - x[i], x[i])*2;
	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    ll t[n+1];
    double v[n+2],m;
    t[0]=v[0]=v[n+1]=0;
    for(int i=1;i<=n;i++){cin>>t[i];t[i]*=2;t[i]+=t[i-1];}
    ll tmax=t[n];vector<double> ans(tmax+1,1e18);
    for(int i=1;i<=n;i++){
        cin>>v[i];v[i]*=2;
        m=0;
        for(ll j=t[i-1];j>=0;j--,m++)ans[j]=min(ans[j],v[i]+m);
        for(ll j=t[i-1];j<=t[i];j++)ans[j]=min(ans[j],v[i]);
        m=0;
        for(ll j=t[i];j<=tmax;j++,m++)ans[j]=min(ans[j],v[i]+m);
    }
    m=0;
    for(ll i=0;i<=tmax;i++,m++){
        ans[i]=min(ans[i],m);
    }
    m=0;
    for(ll i=tmax;i>=0;i--,m++){
        ans[i]=min(ans[i],m);
    }
    double sum=-ans[tmax]-ans[0];
    for(int i=0;i<=tmax;i++)sum+=ans[i]*2;
    doublecout(sum/8);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {

    string N;
    cin >> N;
    cout << (N[0] == N[2] ? "Yes" : "No") << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int N;
  int price[12];
  cin >> N;
  for (int i = 0; i < N; i++) cin >> price[i];

  int max_p = 0;
  for (int i = 0; i < N; i++) {
    if (price[i] > max_p) max_p = price[i];
  }

  int res = 0;
  bool flag = false;
  for (int i = 0; i < N; i++) {
    if (price[i] == max_p && flag == false) {
      price[i] /= 2;
      flag = true;
    }
    res += price[i];
  }
  cout << res;

}

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

int main() {
 int a,b,t;
  cin >>a>>b>>t;
  int Time =a;
  int ans =0;
  for(int i=0;Time<t+1;i++){
    Time += a;
    ans += b;
  }
  cout << ans ;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int               long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;

const int N=1000;

vector<int> v[N];

void solve(){
	int n;
	cin>>n;
	
	
	
	int x = 0;
	rep(i,1,1000){
		if(i*(i-1)/2 == n){
			x=i;
			break;
		}
	}
	
	if(!x){
		cout<<"No";
		return;
	}
	
	int cnt = 1;
	rep(i,1,x){
		rep(j,i+1,x+1){
			v[i].pb(cnt);
			v[j].pb(cnt);
			cnt++;
		}
	}
	
	
	
	cout<<"Yes\n";
	cout<<x<<"\n";
	rep(i,1,x+1){
		cout<<(x-1)<<" ";
		for(int y:v[i]) cout<<y<<" ";
		cout<<"\n";
	}
	
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#ifdef SIEVE
		sieve();
	#endif
	#ifdef NCR
		init();
	#endif
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}


Measured memory_bytes: 5196
def w(d):
    n=len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int, input().split())
inf=float('inf')
fuel=[[inf]*N for _ in range(N)]
for i in range(N):
    fuel[i][i]=0
for _ in range(M):
    a,b,c=map(int,input().split())
    fuel[a-1][b-1]=fuel[b-1][a-1]=c
Q=int(input())
ST=[list(map(int, input().split())) for _ in range(Q)]
fuel = w(fuel)
for i in range(N):
    for j in range(N):
        if 0 < fuel[i][j] <= L:
            fuel[i][j]=1
        elif fuel[i][j] != 0:
            fuel[i][j] = inf
fuel = w(fuel)
for st in ST:
    print(fuel[st[0]-1][st[1]-1]-1 if fuel[st[0]-1][st[1]-1] != inf else -1)


Measured memory_bytes: 136152
#include<bits/stdc++.h>
using namespace std;
#define int long long int
typedef long double ld;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define endl '\n'
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mxe max_element
#define mne min_element
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int,int>
#define size(a)  (int)(a.size())
#define fill(s,x,n) vector
 x(n); rep(i,0,n) cin>>x[i];
#define mod 1000000007
#define inf 1000000000
void solve(){
   int n;
   cin>>n;
   vector<vi> a(n,vi(3)), dp(n,vi(3));
   rep(i,0,n){
   	rep(j,0,3){
   		cin>>a[i][j];
   	}
   }
   dp[0][0]=a[0][0];dp[0][1]=a[0][1];dp[0][2]=a[0][2];
   rep(i,1,n){
   	dp[i][0]=max(a[i][0]+dp[i-1][1], a[i][0]+dp[i-1][2]);
   	dp[i][1]=max(a[i][1]+dp[i-1][0], a[i][1]+dp[i-1][2]);
    dp[i][2]=max(a[i][2]+dp[i-1][1], a[i][2]+dp[i-1][0]);
   }
   cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});

 }
 

signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    /*
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);  
    #endif
    */
	int test;
	//cin>>test;
	test=1;
	while(test--){
         solve();
         cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 11264
n,m,c = map(int,input().split())
b = list(map(int,input().split()))
a = [(list(map(int,input().split()))) for i in range(n)]
t = 0

for i in range(n):
    z = 0
    for j in range(m):
        z += a[i][j] * b[j]
    z += c
    if z > 0:
        t += 1

print(t)    

Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200005;
ll n,k,a[maxn],maxv;
int check(int len)
{
	if(!len)
		return 1e9+1;
	ll num=0;
	for(int i=1;i<=n;i++)
		num+=(a[i]-1)/len;
	return num;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxv=max(maxv,a[i]);
	}
	int l=0,r=maxv;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)>k)
			l=mid+1;
		else
			r=mid;
	}
	cout<<l<<endl;
    return 0;
}


Measured memory_bytes: 5124
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long X = Long.parseLong(sc.next());
		sc.close();

		BigDecimal bd1 = new BigDecimal("100");
		BigDecimal bd2 = new BigDecimal("1.01");
		BigDecimal bd3 = new BigDecimal(String.valueOf(X));

		int year = 0;
		while(bd1.compareTo(bd3) == -1) {
			bd1 = bd1.multiply(bd2);
			bd1 = bd1.setScale(0, RoundingMode.DOWN);
			year++;
		}
		System.out.println(year);
	}

}

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

int main()
{
    int a,b;
    for(int i=0; ;i++){
{
    cin>> a >> b;

    if(a==0&&b==0){
break;
}  
 else
{
if(a<b){
  cout<< a << " " << b <<endl;
}  
   else{cout<< b << " " << a <<endl;
}
}
}
    }
    return 0;
}


Measured memory_bytes: 3016
n = int(input())
x = int(n**0.5)+1
cnt = [0]*(n+1)
for i in range(1,x):
    for j in range(1,x):
        for k in range(1,x):
            res = i**2+j**2+k**2+i*j+j*k+k*i
            if res <= n: cnt[res] += 1
for i in range(1,n+1): print(cnt[i])

Measured memory_bytes: 69668
A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0
for a in range(0, A+1):
    for b in range(0, B+1):
        for c in range(0, C+1):
            if X == a*500+b*100+c*50:
                count += 1

print(count)


Measured memory_bytes: 9040
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
 
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  char A[4];
  cin >> A[0] >> A[1] >> A[2] >> A[3];
  int a = A[0] - '0';
  int b = A[1] - '0';
  int c = A[2] - '0';
  int d = A[3] - '0';
  if(a+b+c+d == 7){
    cout << a << '+' << b << '+' << c << '+' << d << "=7" << endl; 
  }
  else if(a+b+c-d == 7){
    cout << a << '+' << b << '+' << c << '-' << d << "=7" << endl;
  }
  else if(a+b-c+d == 7){
    cout << a << '+' << b << '-' << c << '+' << d << "=7" << endl;
  }
  else if(a+b-c-d == 7){
    cout << a << '+' << b << '-' << c << '-' << d << "=7" << endl;
  }
  else if(a-b+c+d == 7){
    cout << a << '-' << b << '+' << c << '+' << d << "=7" << endl;
  }
  else if(a-b+c-d == 7){
    cout << a << '-' << b << '+' << c << '-' << d << "=7" << endl;
  }
  else if(a-b-c+d == 7){
    cout << a << '-' << b << '-' << c << '+' << d << "=7" << endl;
  }
  else{
    cout << a << '-' << b << '-' << c << '-' << d << "=7" << endl;
  }
}

Measured memory_bytes: 256
#!/usr/bin/env python

n, y = map(int, input().split())
# print(n, y)

found = False
for i in range(n+1):
    for j in range(n+1):
        if i + j > n:
            break
        k = n - (i + j)
        if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
            found = True
            print("{} {} {}".format(i, j, k))
            break
    if found:
        break

if not found:
    print("-1 -1 -1")


Measured memory_bytes: 3060
//@author KhaledAlam.net
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef stringstream ss;
typedef pair<int, int> pii;
//#########################
#define fi           first
#define se           second
#define pb           push_back
#define mp           make_pair
#define out(x)       return cout<<x,0
#define all(x)       x.begin(),x.end()
#define sz(x)        ((int)(x.size()))
#define clr(x)       memset(x,0,sizeof x)
#define rep(i,n)     for(int i=0;i<n;i++)
#define debug(x)     cerr<<"[l#: "<<__LINE__<<"] "<<#x<<" = "<<x<<endl
// v0.0.2 | Github.com/khaledalam/templates/tree/master/cpp
//##########################################################################

#define maxn 101010

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


	string s;
	cin >> s;
	cout
			<< (s.size() == 4
					&& ((s[0] == s[1] && s[0] == s[2])
							|| (s[1] == s[2] && s[1] == s[3])) ? "Yes" : "No");

}



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

int main()
{
    long int n,k;
    cin>>n>>k;
    vector<long int> a(n);
    for(long int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    long int k1=INT_MAX;
    for(long int i=0;i<=n-k;i++)
    {
        long int k2=a[i+k-1]-a[i];
        if(k2<k1)
        {
            k1=k2;
        }
    }
    cout<<k1<<endl;
    return 0;
}


Measured memory_bytes: 3560
//agc002_b.cpp
//Sat Jul 27 14:19:35 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,m;
	cin >> n >> m;

	int ball[n];
	fill(ball,ball+n,1);
	int red[n];
	fill(red,red+n,0);
	red[0] = 1;

	for (int i=0;i<m;i++){
		int x,y;
		cin >> x >> y;
		x--;y--;
		if (red[x]==1){
			red[y] = 1;
		}
		ball[x] = max(0,ball[x]-1);
		ball[y]++;
		if (ball[x]==0){
			red[x] = 0;
		}
	}

	int ans = 0;
	for (int i=0;i<n;i++){
		ans += red[i];
	}

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 1024
n,k = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i)

hash = {}
a_arr.each do |a|
  hash[a] ||= 0
  hash[a] += 1
end

arr = hash.to_a.sort_by{|a, count| -count}[k..-1]

result = 0
arr&.each do |(a, count)|
  result += count
end

puts result


Measured memory_bytes: 45184
<?php
$n = trim(fgets(STDIN));
$k = explode(" ",trim(fgets(STDIN)));
$s = array_sum($k);
rsort($k);

$i = 1;
$p =$k[0];
$s -= $p;
while($i < $n){
$q = $k[$i];
if($p > $s * 2){
break;
}
$s -= $q;
$p = $q;
++$i;
}
echo $i;
?>

Measured memory_bytes: 23876
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int gcd(int x, int y) { return (x % y) ? gcd(y, x % y) : y; }
const double PI = 3.14159265358979323846;
int main() {
  int a, b;
  cin >> a >> b;
  cout << a * b;
  // cout << cos(aida);
}

Measured memory_bytes: 3624