akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define per(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define INF 2e9
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];

    vector<ll> ab;
    rep(i, x) {
        rep(j, y) {
            ab.push_back(a[i]+b[j]);
        }
    }
    sort(all(ab));
    sort(all(c));

    vector<ll> abc;
    rep(i, k) {
        if (x*y-1 < i) break;
        rep(j, k) {
            if (z-1 < j) break;
            abc.push_back(ab[x*y-1-i] + c[z-1-j]);
        }
    }

    sort(all(abc), greater<ll>());
    rep(i, k) {
        cout << abc[i] << endl;
    }

}

Measured memory_bytes: 43112
import java.util.*;

public class Main {
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        int ans = 0;
        int n = sc.nextInt();
        String a = sc.next();
        String b = sc.next();
        String c = sc.next();
        for (int i = 0; i < n; i++) {
            HashSet<Character> se = new HashSet<Character>();
            se.add(a.charAt(i));
            se.add(b.charAt(i));
            se.add(c.charAt(i));
            ans += (se.size() - 1);
        }
        System.out.println(ans);
        sc.close();
    }
}

Measured memory_bytes: 35776
#include<cstdio>
int main()
{
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if(a+b==c||a+c==b||b+c==a)
	{
		printf("Yes\n");
	}
	else
	printf("No\n");
	return 0;
}

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

using namespace std;

typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<llint, llint> pll;
typedef vector<int> vi;
typedef vector<llint> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define ci cin
#define co cout
#define en endl
#define ln cout<< '\n'
#define rep(i, n) for(int i = 0; i < n; i++)
#define outl(x) cout<< (x) << '\n'
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

template<typename Tn> Tn gcd(Tn a, Tn b)
{
    return (b ? gcd(b, a % b) : a);
}

template<typename Tn> Tn lcm(Tn a, Tn b)
{
    return a / gcd(a, b) * b;
}

string IntToString(int number)
{
    stringstream ss;
    ss << number;
    return ss.str();
}

llint cnt = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main()
{
    int a;
    vi v;
    int sum = 0;

    rep(i, 5) {
	ci >> a;
	sum += a;
	
	if(a % 10 == 0) v.pb(0);
	else v.pb(10 - a % 10);
    }
    
    sort(v.begin(), v.end());
    rep(i, v.size() - 1) sum += v[i];

    co << sum << en;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

//約数列挙
template <class T>
vector<T> divisor(T x){
	vector<T> res;
	for(T i=1;i*i<=x;i++){
		if(x%i==0){
			res.push_back(i);
			if(i!=x/i){
				res.push_back(x/i);
			}
		}
	}
	return res;
}

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vector<ll> ret=divisor(n);
	ll ans=0;
	for(auto k:ret){
		if(k==1) continue;
		ll now=n;
		while(now%k==0){
			now/=k;
		}
		if(now%k==1){
			ans++;
		}
	}
	ret=divisor(n-1);
	ans+=(ll)ret.size()-1;
	cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;

int main() {
  int n, ans, t;
  int dp[2][1000];
  char cbuf[1080];

  while (1) {
    scanf("%d\n", &n);
    if (!n) break;
    ans = 0;
    memset(&dp[0][0], 0, sizeof(int)*n);
    memset(&dp[1][0], 0, sizeof(int)*n);
    for (int i=0; i<n; i++) {
      fgets(cbuf, sizeof(cbuf), stdin);
      dp[i&1][0] = (cbuf[0]=='.') ? 1 : 0;
      for (int j=1; j<n; j++) {
        if (cbuf[j] == '.') {
          t = min(dp[i&1][j-1], min(dp[(i+1)&1][j-1], dp[(i+1)&1][j]))+1;
          dp[i&1][j] = t;
          if (ans < t) ans = t;
        } else {
          dp[i&1][j] = 0;
        }
      }
    }
    printf("%d\n", ans);
  }
  
  return 0;
}

Measured memory_bytes: 1056
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


#define MAXN 500000

bitset<MAXN + 1 + 1> b;
bool full[MAXN + 1 + 1];
int lowest = -1;


bool ok(int depth) {
	if (b[0])return false;
	return depth > MAXN || !full[depth] || depth >= lowest;
}

void add(int depth) {
	lowest = max(lowest, depth);
	if (depth >= MAXN)return;
	while (1) {
		if (b[depth]) {
			b.reset(depth--);
		}
		else {
			b.set(depth);
			break;
		}
	}
	if (lowest <= MAXN && !b[lowest])lowest = depth;
	if (depth == 0)return;
	while (full[depth-1] && !full[depth] && b[depth]) {
		full[depth++] = true;
	}
}



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

	full[0] = true;
	int n;
	cin >> n;
	rep(i,n) {
		int x;
		cin >> x;
		if (ok(x)) {
			add(x);
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 3388
use strict;
use warnings;

my $in = <>;
chomp $in;

my $mod = 10 ** 9 + 7;

my $c10 = 1;
my $c09 = 1;
my $c08 = 1;

foreach (1 .. $in){
	$c10 = $c10 * 10 % $mod;
	$c09 = $c09 *  9 % $mod;
	$c08 = $c08 *  8 % $mod;
}

my $ret = $c10 - ($c09 * 2) + $c08 + $mod;
$ret %= $mod;

print $ret;

exit;


Measured memory_bytes: 5104
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}
using namespace std;
int main(){ 
   string s;
   cin>>s;
   int a,z;
   for(int i=0;i<s.size();i++){
      if(s[i]=='A'){
         a=i;
         break;
      }
   }
   for(int i=s.size()-1;i>=0;i--){
      if(s[i]=='Z'){
         z=i;
         break;
      }
   }
   cout<<z-a+1;

   






return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    int A[2], K;
    cin >> A[0] >> A[1] >> K;
    for (int i = 0; i < K; i++) {
        int t = i % 2;
        A[1 - t] += A[t] / 2;
        A[t] -= A[t] / 2 + (A[t] % 2);
    }
    cout << A[0] << " " << A[1] << endl;
}


Measured memory_bytes: 764
#include<iostream>
#include<math.h>

using namespace std;

int main() {

	double x1 = 0;
	double x2 = 0;
	double y1 = 0;
	double y2 = 0;
	double ans = 0;

	cin >> x1 >> y1 >> x2 >> y2;

	ans = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));

	cout << fixed << ans << endl;


}


Measured memory_bytes: 3244
from collections import Counter
import sys

N=int(input())
cards=list(map(int,sys.stdin.readline().strip().split()))
c=Counter(cards)

even=len([x for x in iter(c) if c[x]%2==0])
odd=len([x for x in iter(c) if c[x]%2==1])

print(even-(even%2)+odd)

Measured memory_bytes: 21904
// In the name of god
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <bitset>
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
using namespace std;
 
template <typename T>
T next_int() {
    T x = 0, p = 1;
    char ch;
    do { ch = getchar(); } while(ch <= ' ');
    if(ch == '-') {
        p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return p * x;
}
 
string next_token() {
    char ch;
    string ans = "";
    do { ch = getchar(); } while(ch <= ' ');
    while(ch > ' ') {
        ans += ch;
        ch = getchar();
    }
    return ans;
}
 
const long long INF = (long long)1e18;
const int INFINT = (int)1e9 + 227 + 1;
const int MAXN = (int)1e6 + 227 + 1;    
const int MOD = (int)1e9 + 7;
const long double EPS = 1e-9;
 
long long bin_pow(long long a, long long b) {
    if(!b) return 1;
    long long ans = bin_pow(a, b / 2);
    ans = ans * ans % MOD;
    if(b % 2) ans = ans * a % MOD;
    return ans;
}

int main() {
    // freopen(".in", "r", stdin);

    string a; cin >> a;

    int ans = INFINT;
    for(char c = 'a'; c <= 'z'; c++) {
        string b = a;

        while(1) {
            int heh = 0;
            for(int i = 0; i < b.size(); i++)
                if(b[i] == c) 
                    heh++;

            if(heh == b.size()) break;

            string e = "";
            for(int i = 0; i + 1 < b.size(); i++)
                if(b[i] == c || b[i + 1] == c)
                    e += c;
                else
                    e += b[i];
            
            b = e;
        }

        ans = min(ans, (int)a.size() - (int)b.size());
    }

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


Measured memory_bytes: 256
from collections import Counter 
n=int(input())
a=list(map(int,input().split()))

arr=Counter(a).most_common()

cnt=0
for i in arr:
  if i[0]>i[1]:
    cnt+=i[1]
  elif i[0]<i[1]:
    cnt+=i[1]-i[0]
print(cnt)

Measured memory_bytes: 21232
n = int(input())
lis = []
#print(n)
alf = ""

while n > 0:
    n -= 1
    mod = n % 26
    lis.insert(0,mod)
    n = n // 26
    #print(n)

for i in lis:
   alf += chr(ord("a") + i)
print(alf)

Measured memory_bytes: 9024
#include <iostream>
#include <set>

using namespace std;

int main() {
  int n;

  cin >> n;

  set<string> S;

  for (int i = 0; i < n; i++) {
    string cmd, str;
    cin >> cmd >> str;

    if(cmd == "insert") {
      S.insert(str);
    } else if (cmd == "find") {
      if(S.find(str) != S.end()){
        cout << "yes" << endl;
      } else {
        cout << "no" << endl;
      }
    }
  }

  return 0;
}



Measured memory_bytes: 32104
#include <iostream>
#include<stack>
#include<string>
#include<stdio.h>
#include<algorithm>
using namespace std;
int merges(int start,int end) {
	int middle;
	if (start + 1 < end) {

		middle = (start + end) / 2;
		return (merges(start, middle) + merges(middle , end)-start+end);
	}
	else { return 0; }
}

int main()
{
	int n, dat[500000]; cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> dat[i];
	}
	sort(dat, dat + n);
	for (int i = 0; i <n; i++)
	{
		if (i != 0) {
			cout << " ";
		}
		cout << dat[i];
	}
	
	cout << endl << merges(0, n) << endl;
	return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back

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

int a[100001];
int main(){
	int n;
	cin>>n;
	
	for (int i = 0; i < n; ++i){
		int x;
		cin>>x;
		a[x]++;
	}


	int ans=0;
	for (int i = 1; i < 100000; ++i){
		ans=max(ans,a[i-1]+a[i]+a[i+1]);
	}

	cout<<ans<<endl;

	return 0;
}


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

#define FOR(i, a, b) for(long long int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;



int main(void) {
	int prime[20000] = {};
	int pos = 2;
	prime[1] = 2;
	FOR(i, 3, 200000) {
		bool flag = true;
		FOR(t, 2, sqrt(i) + 1) {
			if (i%t == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			prime[pos] = i;
			pos++;
		}
	}
	
	while (1) {
		int n, p;
		int now;
		int count = 0;
		vector<int>dp(1326, 0);

		cin >> n >> p;
		if (p == -1) {
			break;
		}
		FOR(i, 1, pos) {
			if (prime[i] > n) {
				now = i;
				break;
			}
		}
		FOR(i, now, now + 50) {
			FOR(t, i, now + 50) {
				dp[count] = prime[i] + prime[t];
				count++;
			}
		}
		/*FOR(i, 0, 1325) {
			cout << dp[i] << endl;
		}*/
		sort(dp.begin(), dp.end());
		/*cout << endl;
		FOR(i, 0, 1325) {
			cout <<i<<" "<< dp[i] << endl;
		}
		cout << endl;*/
		cout << dp[p - 1] << endl;
	}
	
}


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

void dfs(long n,set<long> &s){
    s.insert(n);
    if(n < 323456667){
        int sita = n%10;
        dfs(n*10 + sita,s);
        if(sita > 0){
            dfs(n*10 + sita - 1,s);
        }
        if(sita < 9){
            dfs(n*10 + sita + 1,s);
        }
    }
}



int main(){
    int k;
    cin >> k;
    
    set<long>s;

    for(long i=1;i<=9;i++)dfs(i,s);
    auto it = s.begin();
    for(int i=0;i<k-1;i++)it++;
    cout << *it << endl;
    

    

}

Measured memory_bytes: 8308
#include <bits/stdc++.h>
    using namespace std;
     
    int main(){
      int a,b;
      cin >> a >> b;
      if(a%2==0){
        if(b<=a/2){cout << "YES" << endl;}
        else cout << "NO" << endl;
      }else{
        if(b<=1+(a/2)){cout << "YES" << endl;}
        else cout << "NO" << endl;
      }
      return 0;
    }

Measured memory_bytes: 256
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
a3 = list(map(int, input().split()))
n = int(input())
b_lst = [int(input()) for _ in range(n)]
a_lst = a1 + a2 + a3

for i in range(len(b_lst)):
    if b_lst[i] in a_lst:
        a_lst[a_lst.index(b_lst[i])] = 0

ans = 0

for i in range(3):
    if a_lst[i] == a_lst[i+3] == a_lst[i+6] == 0:
        print("Yes")
        ans = 1
        break
    elif a_lst[3*i] == a_lst[3*i+1] == a_lst[3*i+2] == 0:
        print("Yes")
        ans = 1
        break
    elif a_lst[2] == a_lst[4] == a_lst[6] == 0 or a_lst[0] == a_lst[4] == a_lst[8] == 0:
        print("Yes")
        ans = 1
        break

if ans == 0:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define maxn 100086

using namespace std;

const int p = 1e9 + 7;

int n;

int main(){
	scanf("%d", &n);
	int x = 1, y = 1, z = 1;
	for(int i = 1;i <= n;i++) x = 1ll * x * 10 % p, y = 1ll * y * 9 % p, z = 1ll * z * 8 % p;
	printf("%d", (1ll * x + 2 * p - 2 * y + z) % p);
}

Measured memory_bytes: 3828
from functools import reduce
from fractions import gcd
N, X = map(int, input().split())
x = [int(xi) for xi in input().split()]
x.append(X)
x = sorted(x)
diffs = [x[i+1] - x[i] for i in range(N)]
if len(diffs) == 1:
    print(diffs[0])
else:
    print(reduce(gcd, diffs))



Measured memory_bytes: 16308
import java.util.*;
public class Main{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        ArrayList<String> test_case = new ArrayList<>();
        int n = sc.nextInt();
        for (int i = 0; i < n+1; i++) {
            test_case.add(sc.nextLine());
        }
        Map<String,Integer> sum = new HashMap<>();
        sum = solve(test_case);

        System.out.println("AC x " + sum.get("AC") + System.getProperty("line.separator")
                + "WA x " + sum.get("WA") + System.getProperty("line.separator")
                + "TLE x " + sum.get("TLE") + System.getProperty("line.separator")
                + "RE x " + sum.get("RE")
                );
    }

    public static Map<String,Integer> solve (ArrayList<String> test_case){
        Map<String,Integer> sum = new HashMap<>();
        int ac = 0;
        int tle = 0;
        int wa = 0;
        int re = 0;
        sum.put("AC", ac);
        sum.put("TLE", tle);
        sum.put("RE", re);
        sum.put("WA", wa);

        for (String test : test_case) {
            switch(test){
                case "AC":
                    ac++;
                    sum.put("AC",ac);
                    break;
                case "TLE":
                    tle++;
                    sum.put("TLE",tle);
                    break;
                case "WA":
                    wa++;
                    sum.put("WA",wa);
                    break;
                case "RE":
                    re++;
                    sum.put("RE",re);

            }
        }
        return sum;
    }

}

Measured memory_bytes: 67100
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define pi 3.14159265359
# define str string
# define vll vector<ll>
# define vstr vector<str>
# define vpll vector<pair<ll,ll> >
//assign() assignes new value
//emplace(position,x) inserting
//erase(position) to remove an element
//swap() for swapping
//reverse(position,position) for reversing
# define pb push_back
# define popb pop_back
# define pf push_front
# define popf pop_front
# define sll set<ll>
//find()
//erase(x) removes element x
//erase(position,position)
# define qll queue<ll>
# define qstr queue<str>
//front(),back()
# define stll stack<ll>
# define ststr stack<str>
//top()
# define dll deque<ll>
//at()
# define mll map<ll,ll>
# define msl map<str,ll>
# define mls map<str,ll>
# define mstr map<str,str>
# define mcl map<char,ll>
# define pll pair<ll,ll>
# define f(x,y) for(int x=0;x<y;x++)
# define r(x,y) for(int x=y;x>=0;x--)
# define fr(x,y,z) for(int x=y;x<z;x++)
# define rr(x,y,z) for(int x=y;x>z;x--)
ll gcd(ll a, ll b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a, b);
}
void print(vll a){
    for(int i=0;i<a.size();i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
}
vll inp(int n){
    vll a;
    ll x;
    f(i,n){
        cin>>x;
        a.pb(x);
    }
    return a;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t,n,i,j,k,l,c,c1,c2,cnt,flag,m1,m,m2,maxi,mini,x,y,z,p,q,r;
    vll a,b;
    str s,s1,s2;
    cin>>n;
    cin>>p>>q>>r;
    for(i=1;i<n;i++){
        cin>>x>>y>>z;
        c=x+max(q,r);
        c1=y+max(p,r);
        c2=z+max(p,q);
        p=c,q=c1,r=c2;
    }
    cout<<max(p,max(q,r))<<endl;   
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;

  for (int i = 0; i <= n - 3; i++) {
    if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3552
#include<iostream>
#include<algorithm>
#include<complex>
using namespace std;
typedef long long ll;
#define N 3010
#define M 1010
#define chmax(a,b) a=max(a,b);
ll n,m,v[N],h[N],t[M],s[M];
ll f[M][N],g[M][N],l[M];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>h[i];
    for(int i=1;i<=m;i++)cin>>t[i]>>s[i]; s[0]=0;
    
    ll p=0,sum=0; l[0]=0;
    for(int i=1;i<=m;i++){
	for(;p<=n&&sum+v[p]<=t[i];p++)sum+=v[p];
	l[i]=p;
    }
    //cout<<"l:";for(int i=0;i<=m;i++)cout<<l[i]<<" ";cout<<endl;
    
    for(int i=0;i<M;i++)for(int j=0;j<N;j++)f[i][j]=g[i][j]=-1e17;
    f[0][0]=0;
    for(int i=0;i<m;i++){
	for(int j=0;j<=l[i+1];j++){
	    if(i>0){
		if(j<n)chmax(g[i][j+1],g[i][j]+h[j+1]+abs(h[j+1]-h[j]));
		chmax(f[i][j],g[i][j]);
	    }
	    if(f[i][j]>=s[i]){
		chmax(f[i+1][j],f[i][j]);
		if(j<n)chmax(g[i+1][j+1],f[i][j]+h[j+1]);
	    }
	}
    }
    /*
    for(int i=0;i<=m;i++){
	for(int j=0;j<=n;j++)cout<<f[i][j]<<" ";
	cout<<endl;
    }*/
    ll ans=-1;
    for(int i=0;i<=n;i++){
	if(f[m][i]>=s[m]){
	    ans=t[m];
	    for(int j=1;j<=i;j++)ans-=v[j];
	    break;
	}
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 50672
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n;
    string s;
    cin >> n >> s;
    int E[n] = {},W[n] = {};
    int E_count = 0,W_count = 0;
    for(int i = 0;i < n;i++)
    {
        if(s[i] == 'E')
        {
            E_count++;
        }
        E[i] = E_count;
        if(s[n - 1 - i] == 'W')
        {
            W_count++;
        }
        W[n - 1 - i] = W_count;
    }
    int Max = W[1];
    for(int i = 1;i < n - 1;i++)
    {
        if(E[i - 1] + W[i + 1] > Max)
        {
            Max = E[i - 1] + W[i + 1];
        }
    }
    if(E[n - 2] > Max)
    {
        Max = E[n - 2];
    }
    cout << n - Max - 1 << "\n";

    return 0;
}

Measured memory_bytes: 2948
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;
    vector<string> v{"Sunny", "Cloudy", "Rainy"};
    for (int i = 0; i < 3; i++) {
        if (v[i] == s)cout << v[(i + 1) % 3] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
fn solve(graph: Vec<Vec<usize>>) -> Vec<usize> {
    let size = graph.len();
    let mut assign = vec![size + 1; size];
    let mut preorder = vec![size + 1; size];
    let mut order = 0;
    let mut component = 0;
    for i in 0..size {
        if preorder[i] <= size {
            continue;
        }
        let mut stack = vec![];
        let mut not_assigned = vec![];
        let mut intermidiate = vec![];
        stack.push(i);
        'outer: while !stack.is_empty() {
            let from = *stack.last().unwrap();
            if preorder[from] == size + 1 {
                // Preorder procedure.
                preorder[from] = order;
                order += 1;
                not_assigned.push(from);
                intermidiate.push(from);
            }
            for &to in &graph[from] {
                if preorder[to] == size + 1 {
                    stack.push(to);
                    continue 'outer;
                } else if assign[to] == size + 1 {
                    while let Some(top) = intermidiate.pop() {
                        if preorder[top] <= preorder[to] {
                            intermidiate.push(top);
                            break;
                        }
                    }
                }
            }
            // Postorder.
            let from = stack.pop().unwrap(); // safe.
            let top = intermidiate.pop().unwrap();
            if top == from {
                while let Some(top_of_not_assigned) = not_assigned.pop() {
                    assign[top_of_not_assigned] = component;
                    if top_of_not_assigned == top {
                        break;
                    }
                }
                component += 1;
            } else {
                intermidiate.push(top);
            }
        }
    }
    assign
}

use std::io::{BufRead, BufReader};
fn main() {
    let mut read = BufReader::new(std::io::stdin())
        .lines()
        .filter_map(|e| e.ok());
    let (v, e) = {
        let line = read.next().unwrap();
        let line: Vec<&str> = line.split(' ').collect();
        let v: usize = line[0].parse().unwrap();
        let e: usize = line[1].parse().unwrap();
        (v, e)
    };
    let graph = {
        let mut graph: Vec<Vec<_>> = vec![vec![]; v]; // Adj list
        for _ in 0..e {
            let edge = read.next().unwrap();
            let mut edge = edge.split(' ');
            let start: usize = edge.next().unwrap().parse().unwrap();
            let end: usize = edge.next().unwrap().parse().unwrap();
            graph[start].push(end);
        }
        graph
    };
    let component = solve(graph);
    read.next();
    for line in read {
        let line: Vec<_> = line.split(' ').collect();
        let start: usize = line[0].parse().unwrap();
        let end: usize = line[1].parse().unwrap();
        if component[start] == component[end] {
            println!("1");
        } else {
            println!("0");
        }
    }
}



Measured memory_bytes: 5044
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int Maxn = 20004;
const int Maxm = 100000;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x7FFFFFFF;

struct MinCostMaxFlow_Dinic {
	struct Edge {
		int to, cap;
		ll cos;
		Edge *nxt, *bak;
	};
	Edge pool[Maxm + 5];
	Edge *ecnt, *G[Maxn + 5];
	inline void addedge(int u, int v, int cap, ll c) {
		Edge *p = ++ecnt;
		p->to = v, p->cap = cap, p->cos = c;
		p->nxt = G[u], G[u] = p;
		p->bak = p + 1;
		p = ++ecnt;
		p->to = u, p->cap = 0, p->cos = -c;
		p->nxt = G[v], G[v] = p;
		p->bak = p - 1;
	}
	int node, s, t;
	ll d[Maxn + 5];
	Edge *cpy[Maxn + 5];
	ll cost;
	void init(int n) {
		ecnt = &pool[0];
		node = n;
		for(int i = 1; i <= n; i++)
			G[i] = NULL;
	}
	bool vis[Maxn + 5];
	int dfs(int u, int tot) {
		if(u == t) return tot;
		vis[u] = true;
		int sum = 0;
		for(;cpy[u] != NULL; cpy[u] = cpy[u]->nxt) {
			int v = cpy[u]->to, w = cpy[u]->cos;
			if(!vis[v] && d[v] == d[u] + w && cpy[u]->cap > 0) {
				int delta = dfs(v, min(tot - sum, cpy[u]->cap));
				cpy[u]->cap -= delta, cpy[u]->bak->cap += delta;
				cost += cpy[u]->cos * delta;
				sum += delta;
				if(sum == tot) break;
			}
		}
		vis[u] = false;
		return sum;
	}
	bool spfa(int _s, int _t) {
		static bool inq[Maxn + 5];
		memset(inq, false, sizeof inq);
		for(int i = 0 ; i <= node; i++)
			d[i] = -INFLL, cpy[i] = G[i];
		queue<int> q;
		q.push(_s), d[_s] = 0, inq[_s] = true;
		while(!q.empty()) {
			int u = q.front();
			q.pop(), inq[u] = false;
			for(Edge *p = G[u]; p != NULL; p = p->nxt) {
				int v = p->to;
				if(p->cap > 0 && d[v] < d[u] + p->cos) {
					d[v] = d[u] + p->cos;
					if(!inq[v]) {
						inq[v] = true;
						q.push(v);
					}
				}
			}
		}
		return d[_t] != -INFLL;
	}
	ll mcmf(int _s, int _t) {
		s = _s, t = _t, cost = 0;
		while(spfa(s, t)) {
			memset(vis, false, sizeof vis);
			dfs(s, INF);
		}
		return cost;
	}
};

int N;
MinCostMaxFlow_Dinic f;

int main() {
#ifdef LOACL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	scanf("%d", &N);
	int S = 1, T = 2 * N + 6;
	f.init(2 * N + 6);
	for(int i = 1; i <= N; i++) {
		int x, y, val;
		scanf("%d %d %d", &x, &y, &val);
		f.addedge(S, i + 1, val, 0);
		f.addedge(i + 1, N + 2, INF, x + y);
		f.addedge(i + 1, N + 3, INF, -x + y);
		f.addedge(i + 1, N + 4, INF, x - y);
		f.addedge(i + 1, N + 5, INF, -x - y);
	}
	for(int i = 1; i <= N; i++) {
		int x, y, val;
		scanf("%d %d %d", &x, &y, &val);
		f.addedge(i + N + 5, T, val, 0);
		f.addedge(N + 2, i + N + 5, INF, -x - y);
		f.addedge(N + 3, i + N + 5, INF, x - y);
		f.addedge(N + 4, i + N + 5, INF, -x + y);
		f.addedge(N + 5, i + N + 5, INF, x + y);
	}
	printf("%lld\n", f.mcmf(S, T));
	return 0;
}

Measured memory_bytes: 1024
import copy
list = []
n = int(input())
for i in range(n):
    list.append(int(input()))
list2 = copy.deepcopy(list)
maxsize = max(list)
list2.sort(reverse=True)
max_second = list2[1]
maxsecond = list2[1]
for j in range(n):
    a = list[j]
    if a == maxsize:
        print(maxsecond)
    else:
        print(maxsize)

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

int main() {
	int N, M ,ai ,bi ;
	cin >> N >>M ;
	vector <int> sum(N,0) ;
	for (int i=0; i<M; i++){
		cin >>ai>>bi;
		sum.at(ai-1)++;
		sum.at(bi-1)++;
	}
	
	for (int i=0;i<N;i++){
		cout << sum.at(i)<<endl;
	}
	
}

Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

template<class T>
struct Edge {
	int to;
	T cost;
	Edge() {}
	Edge(int to, T cost) : to(to), cost(cost) {}
	bool operator>(const Edge &r) const { return this->cost > r.cost; }
};

template<class T>
vector<T> Dijkstra(const vector<vector<Edge<T>>> &edges, const int st) {

	const int V = (int)edges.size();
	const T inf = numeric_limits<T>::max() / 2;
	vector<T> cost(V, inf);
	cost[st] = 0;

	priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> pq;
	pq.emplace(st, cost[st]);

	while (!pq.empty()) {

		Edge<T> now(pq.top().to, pq.top().cost);
		pq.pop();

		if (cost[now.to] < now.cost) continue;
		for (const Edge<T> &e : edges[now.to]) {
			T tmp_cost = now.cost + e.cost;
			if (cost[e.to] > tmp_cost) {
				cost[e.to] = tmp_cost;
				pq.emplace(e.to, cost[e.to]);
			}
		}
	}

	return cost; // min cost to vertex idx from st
}

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;


	vector<vector<Edge<lint>>> edges(N);
	for (int i = 0; i < M; i++) {
		lint u, v, len;
		cin >> u >> v >> len;
		u--, v--;
		edges[u].emplace_back(v, len);
	}

	for (int i = 0; i < N - 1; i++) edges[i + 1].emplace_back(i, 0);

	lint ans = Dijkstra(edges, 0)[N - 1];
	if (ans < LINF / 2) cout << ans << "\n";
	else cout << -1 << "\n";

	return 0;
}

Measured memory_bytes: 9336
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
// typedef __int128_t Int;
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

int N, M;
bool inrange(int x, int y) { return 0 <= x and x < N and 0 <= y and y < M; }
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  cin >> N >> M;
  int ans = 0;
  if (N == 1 and M == 1) {
    ans = 1;
  } else if (N == 1) {
    ans += max(0ll, M - 2);
  } else if (M == 1) {
    ans += max(0ll, N - 2);
  } else if (N >= 3 and M >= 3) {

    ans += max(0ll, N - 2) * max(0ll, M - 2);
  } else {
    vector<vector<int>> v(N, vector<int>(M, 0));
    int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
    rep(i, 0, N) rep(j, 0, M) {
      v[i][j]++;
      rep(k, 0, 8) {
        int x = i + dx[k], y = j + dy[k];
        if (inrange(x, y))
          v[x][y]++;
      }
    }
    rep(i, 0, N) rep(j, 0, M) if (v[i][j] & 1) ans++;
  }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,count=0;
cin>>n;
string s;
cin>>s;
string s1=s;
sort(s.begin(),s.end());
for(int i=0;i<s.size();i++){
	if(s[i]!=s1[i]){
		count++;
	}
}
cout<<count/2<<endl;

	return 0;
}

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

#define rep(i,n) for(int (i)=0,temp=(int)(n);(i)<temp;++(i)) 
#define all(x) (x).begin(),(x).end()
#define vint vector<int>

signed main(void){
  string s;cin>>s;
  int n=s.length();
  vint v(n);
  rep(i,n)v[i]=s[n-i-1]-'0';
  v.push_back(0);
  rep(i,n){
    if(v[i]>5||v[i]==5&&v[i+1]>=5){
      v[i+1]++;
      v[i]=10-v[i];
    }
  }
  cout << accumulate(all(v),0LL) << endl;
}


Measured memory_bytes: 10884
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <iomanip>
#include <stdio.h>
#include <bitset>

typedef long long ll;

constexpr long long INFLL = 1e18;

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i++)
    {
        cin >> a.at(i);
    }

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

    ll ans = 0;
    ans = a.at(0);

    for (int i = 2; i < n; i++)
    {
        ans += a.at(floor(i / 2));
    }

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

Measured memory_bytes: 3680
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> odd(200000), even(200000);
    for(int i=0; i<n; i++) {
        int v;
        cin >> v;
        if(i%2) {
            odd[v]++;
        } else {
            even[v]++;
        }
    }

    int odd_max_pos = distance(odd.begin(), max_element(odd.begin(), odd.end()));
    int odd_max_val = *max_element(odd.begin(), odd.end());
    *max_element(odd.begin(), odd.end()) = 0;
    int odd_sec_pos = distance(odd.begin(), max_element(odd.begin(), odd.end()));
    int odd_sec_val = *max_element(odd.begin(), odd.end());

    int even_max_pos = distance(even.begin(), max_element(even.begin(), even.end()));
    int even_max_val = *max_element(even.begin(), even.end());
    *max_element(even.begin(), even.end()) = 0;
    int even_sec_pos = distance(even.begin(), max_element(even.begin(), even.end()));
    int even_sec_val = *max_element(even.begin(), even.end());

    if(odd_max_pos == even_max_pos) {
        cout << n - max(odd_max_val + even_sec_val, odd_sec_val + even_max_val) << endl;
    } else {
        cout << n - odd_max_val - even_max_val << endl;
    }
    return 0;
}


Measured memory_bytes: 1792
module Main where

import Data.Functor

main :: IO ()
main = do
  { [a,b] <- getInts
  ;if a < b then putStrLn "a < b"
   else if a > b then putStrLn "a > b"
        else  putStrLn "a == b"
  }

getInts :: IO [Int]
getInts = map read . words <$> getLine

Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int E = sc.nextInt();
            int Y = sc.nextInt();

            if ( E == 0 ) {
                Y -= 1867;
                if ( Y <= 44 ) {
                    System.out.println("M" + Y);
                    continue;
                }
                Y -= 44;
                if ( Y <= 14 ) {
                    System.out.println("T" + Y);
                    continue;
                }
                Y -= 14;
                if ( Y <= 63 ) {
                    System.out.println("S" + Y);
                    continue;
                }
                Y -= 63;
                System.out.println("H" + Y);
            } else {
                Y += 1867;
                if ( E > 1 ) {
                    Y += 44;
                }
                if ( E > 2 ) {
                    Y += 14;
                }
                if ( E > 3 ) {
                    Y += 63;
                }
                System.out.println(Y);
            }
        }
    }
}



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

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;

int get_lcp(string a, string b) {
  int com = 0;
  while (com < (int) a.size() && com < (int) b.size() && a[com] == b[com]) {
    com++;
  }
  return com;
}

const int N = (int) 2e5 + 7;
int n;
int lcp[N];
int lim[N], bg[N];
int t[4 * N];
int f[N][26];
string a[N];
int mn[26][4 * N];
int mx[26][4 * N];

void build(int v, int tl, int tr) {
  if (tl == tr) {
    for (int x = 0; x < 26; x++) {
      mn[x][v] = mx[x][v] = f[tl][x];
    }
    t[v] = lcp[tl];
  } else {
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    t[v] = min(t[2 * v], t[2 * v + 1]);
    for (int x = 0; x < 26; x++) {
      mn[x][v] = min(mn[x][2 * v], mn[x][2 * v + 1]);
      mx[x][v] = max(mx[x][2 * v], mx[x][2 * v + 1]);
    }
  }
}

int get(int v, int tl, int tr, int l, int r) {
  if (tr < l || r < tl) {
    return (int) 1e9;
  }
  if (l <= tl && tr <= r) {
    return t[v];
  }
  int tm = (tl + tr) / 2;
  return min(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
}

void build() {
  build(1, 1, n);
}

int get(int i, int j) {
  if (i == j) {
    cout << "why equal?\n";
    exit(0);
  }
  if (i > j) {
    swap(i, j);
  }
  return get(1, 1, n, i, j - 1);
}

int calc(int v, int tl, int tr, int l, int r, int x, int need) {
  if (tr < l || r < tl) {
    return 0;
  }
  if (l <= tl && tr <= r) {
    if (mn[x][v] >= need) {
      return tr - tl + 1;
    }
    if (mx[x][v] < need) {
      return 0;
    }
  }
  int tm = (tl + tr) / 2;
  return calc(2 * v, tl, tm, l, r, x, need) + calc(2 * v + 1, tm + 1, tr, l, r, x, need);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    reverse(a[i].begin(), a[i].end());
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i < n; i++) {
    lcp[i] = get_lcp(a[i], a[i + 1]);
  }
  for (int i = 1; i <= n; i++) {
    for (auto &ch : a[i]) {
      f[i][ch - 'a']++;
    }
  }
  build();
  for (int i = 1; i <= n; i++) {
    int len = (int) a[i].size();
    int pos = i, lo = i + 1, hi = n;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (get(i, mid) >= len - 1) {
        pos = mid;
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    lim[i] = pos;
    pos = i;
    lo = 1;
    hi = i - 1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (get(mid, i) >= len - 1) {
        pos = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    bg[i] = pos;
  }
  ll sol = 0;
  for (int i = 1; i <= n; i++) {
    int x = a[i].back() - 'a', need = f[i][x];
    int now = calc(1, 1, n, bg[i], lim[i], x, need);
    sol += now - 1;
  }
  cout << sol << "\n";
  return 0;
}


Measured memory_bytes: 141144
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

struct STlazy{
private:
    vector<ll> node, lazy;
    int n;
public:
    STlazy(int siz){
        n = 1;
        while(n < siz)  n *= 2;
        node.resize(2*n-1, 0);
        lazy.resize(2*n-1, 0);
    }

    void eval(int k, int l, int r){
        if(lazy[k] == 0)    return;
        node[k] += lazy[k];
        if(r-l > 1){
            lazy[2*k+1] += lazy[k]/2;
            lazy[2*k+2] += lazy[k]/2;
        }
        lazy[k] = 0;
    }
    
    void add(int a, int b, ll x, int k=0, int l=0, int r=-1){
        if(r < 0)   r = n;
        eval(k, l, r);
        if(r <= a || b <= l)    return;
        if(a <= l && r <= b){
            lazy[k] += (r-l)*x;
            eval(k, l, r);
            return;
        }
        add(a, b, x, 2*k+1, l, (l+r)/2);
        add(a, b, x, 2*k+2, (l+r)/2, r);
        node[k] = node[2*k+1] + node[2*k+2];
    }

    ll query(int a, int b, int k=0, int l=0, int r=-1){
        if(r < 0)   r = n;
        if(r <= a || b <= l)    return 0;
        eval(k, l, r);
        if(a <= l && r <= b)    return node[k];
        ll lx = query(a, b, 2*k+1, l, (l+r)/2);
        ll rx = query(a, b, 2*k+2, (l+r)/2, r);
        return lx+rx;
    }
};

// これでも一応AC
int seg_main(){
    int n, m;
    cin >> n >> m;
    STlazy st(n);
    int bef, aft;
    cin >> bef; bef--;
    for(int i = 1; i < m; i++){
        cin >> aft; aft--;
        st.add(min(bef, aft), max(bef, aft), 1);
        bef = aft;
    }
    ll a, b, c, ans = 0;
    for(int i = 0; i < n-1; i++){
        cin >> a >> b >> c;
        ll tmp = (ll)(st.query(i, i+1));
        ans += min(tmp*a, tmp*b+c);
    }
    cout << ans << endl;
    return 0;
}

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

    int cnt[100002] = {};
    int bef, aft;
    cin >> bef;
    for(int i = 1; i < m; i++){
        cin >> aft;
        cnt[min(bef,aft)]++, cnt[max(bef,aft)]--;
        bef = aft;
    }
    for(int i = 1; i < n+1; i++)    cnt[i] += cnt[i-1];

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

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


Measured memory_bytes: 3508
#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
//#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
  
#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 1000000
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//spfa
//https://cn.vjudge.net/contest/239171#problem/C 

//const int maxn=10005;
//const int inf=0x3f3f3f3f;
int N,M,k;
int head[10100];
int cost[10100],dis[10100];
bool vst[10100];
struct node{
    int to,next,dis,cost;
}edge[50100];

void spfa(int x)
{
	clean(dis,INF);
	clean(vst,0);
	clean(cost,INF);
//    memset(dis,inf,sizeof(dis));
//    memset(vst,0,sizeof(vst));
//    memset(cost,inf,sizeof(cost));
    queue<int> q;
    dis[x]=0;
    cost[x]=0;
    q.push(x);
    while(!q.empty())
	{
        x=q.front();q.pop();
        vst[x]=0;
        for(int i=head[x];i!=-1;i=edge[i].next)
		{
            node b=edge[i];
            if(dis[b.to]>dis[x]+b.dis)
			{
                if(!vst[b.to])
				{
                    vst[b.to]=1;
                    q.push(b.to);
                }
                dis[b.to]=dis[x]+b.dis;
                cost[b.to]=b.cost;
            }
			else if(dis[b.to]==dis[x]+b.dis)
			{
                if(cost[b.to]>b.cost)
                    cost[b.to]=b.cost;
            }
        }
    }
}
void addEdge(int a,int b,int dis,int cost)
{
    edge[k].to=b;
    edge[k].dis=dis;
    edge[k].cost=cost;
    edge[k].next=head[a];
    head[a]=k;
    k++;
}
int main()
{
    while(cin>>N>>M,N)
	{
        clean(head,-1);
        k=0;
        for(int i=0;i<M;i++){
            int a,b,d,c;
            cin>>a>>b>>d>>c;
            addEdge(a,b,d,c);
            addEdge(b,a,d,c);
        }
        spfa(1);
        long long re=0;
        for(int i=1;i<=N;i++){
            re+=cost[i];
        }
        cout<<re<<endl;
    }

    return 0;
}


Measured memory_bytes: 3836
import bisect,collections,copy,heapq,itertools,math,string
import sys
def I():
    #1 line 1 int
     return int(sys.stdin.readline().rstrip())
def LI():
    #1 line n int
     return list(map(int,sys.stdin.readline().rstrip().split()))
def S():
    #1 line 1 string
     return sys.stdin.readline().rstrip()
def LS():
    #1 line n strings
     return list(sys.stdin.readline().rstrip().split())

A=LS()
X=A[0]
Y=A[1]
if X < Y:
    print("<")
elif X==Y:
    print("=")
else:
    print(">")

Measured memory_bytes: 10020
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<list>
#include<set>
#include<string>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
typedef long long ll;

const ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a) {
	long long b = M, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}
int main() {
	ll i, ans=0, count = 0;
	char s[222222];
	cin >> s;
	if (s[0] == 'A')
		count++;
	for (i = 1; s[i] != '\0'; i++) {
		if (s[i] == 'A')
			count++;
		if (s[i] == 'B') {
			if (s[i - 1] != 'A'||s[i+1]!='C')
				count = 0;
		}
		if (s[i] == 'C') {
			if (s[i - 1] == 'B') {
				ans += count;
				s[i] = 'A';
			}
			else
				count = 0;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 5120
from itertools import combinations

def readinput():
    n=int(input())
    s=input()

    return n,s

def main(n,s):
    count=0
    s1=s[:]
    for i in range(10):
        index1=s1.find(str(i))
        if index1 == -1:
            continue
        s2=s1[index1+1:]
        if(len(s2)<2):
            continue
        #print('s2: {}'.format(s2))
        for j in range(10):
            index2=s2.find(str(j))
            if index2 == -1:
                continue
            s3=s2[index2+1:]
            if(len(s3)<1):
                continue
            #print('s3: {}'.format(s3))
            for k in range(10):
                #print(s[index1+index2+1:])
                index3=s3.find(str(k))
                if index3 == -1:
                    continue
                count+=1
                #print(i,j,k)
    return count

if __name__=='__main__':
    n,s=readinput()
    ans=main(n,s)
    print(ans)
     

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    char c;
    cin >> c;
    if(c == 'A'){
        print("T");
    }else if(c == 'T'){
        print("A");
    }else if(c == 'C'){
        print("G");
    }else{
        print("C");
    }


}

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

int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	
	cout<<((a+b>b+c)? ((b+c>c+a)? c+a:b+c):((a+b>c+a)? c+a:a+b))<<endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define inf 1e9+1
#define inf1 1e18+1
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 1000005
#define mid(l,r) l+(r-l)/2
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(a>b)swap(a,b);if(!a)return b;return gcd(b%a,a);}

void solve(){
	string s;
	cin>>s;
	int n=s.length();
	for(int i=0;i<n;i++){
		if(i&1&&s[i]=='R'){cout<<"No";return ;}
		else if(!(i&1)&&s[i]=='L'){cout<<"No";return;}
	}
	cout<<"Yes";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}

Measured memory_bytes: 256