akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef unsigned long long ull;
#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)
#define all(a) (a).begin(), (a).end()

bool ok(int i, int j){
	return i == j && i < 9;
}

int main(){
	string s;
	vector<vector<int> > a, b;
	for(int i=1; i < 10; i++){
		vector<int> v;
		for(int j=0; j< 2; j++) v.push_back(i);
		b.push_back(v);
		v.push_back(i);
		a.push_back(v);
	}
	for(int i=1; i <= 7; i++){
		vector<int> v;
		for(int j=0; j < 3; j++) v.push_back(i+j);
		a.push_back(v);
	}

	while(cin >> s){
		int c[10] = {0};
		for(int i=0; i < s.size(); i++) c[s[i]-'0']++;
		string t = "123456789";

		vector<int> ret;
		rep(q, t.size()){
			c[t[q]-'0']++;
			bool p = true;
			rep(i, 10) if(4 < c[i]){c[t[q]-'0']--; p = false; break;}
			if(!p) continue;
			loop(i, 0, a.size())loop(j, 0, a.size()){
				if(ok(i, j)) continue;
				loop(k, 0, a.size()){
					if(ok(j, k) || ok(i, k)) continue;
					loop(l, 0, a.size()){
						if(ok(i, l) || ok(j, l) || ok(k, l)) continue;
						rep(m, b.size()){
							if(i == m || j == m || k == m || l == m) continue;
							int d[10] = {0};
							rep(n, 3){d[a[i][n]]++; d[a[j][n]]++; d[a[k][n]]++; d[a[l][n]]++;}
							rep(n, 2) d[b[m][n]]++;
							bool possible = true;
							rep(n, 10) if(c[n] != d[n]){possible = false; break;}
							if(possible) ret.push_back(q+1);
						}
					}
				}
			}
			c[t[q]-'0']--;
		}
		int n = -1;
		rep(i, ret.size()){
			if(n != ret[i]){cout << (i == 0 ? "" : " ") << ret[i]; n = ret[i];}
		}
		if(n == -1) cout << 0;
		cout << endl;
	}
}

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


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

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  char c;
  cin >> c;
  if('a'<=c && c<= 'z') cout << "a" << endl;
  else cout << "A" << endl;
 
  return 0;
}

Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
 
 
int main(){
    string n;
    
    cin >> n;
 
    long long sum = 0;
    for(int i = 0; i < n.size(); i++){
        sum += n[i] - '0';
    }
 
    long long ans = sum % 9;
    if(ans == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
 
    return 0;
}

Measured memory_bytes: 3644
#include<stdio.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
    int n,maxx=0,k;
    scanf("%d%d",&n,&k);
    priority_queue<int, vector<int> , greater<int> >q;
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=0; i<=n; i++)
    {
        for(int j=0; (i+j)<=min(n,k); j++)
        {
            int sum=0,nh;
            nh=k-i-j;
            for(int o=1; o<=i; o++)
            {
                sum=sum+a[o];
                q.push(a[o]);
            }
            for(int o=1; o<=j; o++)
            {
                sum=sum+a[n-o+1];
                q.push(a[n-o+1]);
            }
            while(!q.empty()&&nh>0&&q.top()<0)
            {
                sum=sum-q.top();
                q.pop();
                nh--;
            }
            if(sum>maxx)  maxx=sum;
            while(!q.empty())
            {
                q.pop();
            }
        }
    }
    printf("%d\n",maxx);
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

int main() {
  ll n;
  cin >> n;
  ll ans = 0;
  if(n%2 == 1) {
    cout << 0 << endl;
  }else {
    n /= 2;
    ll i = 5;
    while(n >= i) {
    ans += n/i;
    i *= 5;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

int main()
{
	int n;
	scanf("%d", &n);
	int a[200000];
	for (int i = 0; i < n; ++i)
    {
		scanf("%d", a + i);
    }
	std::sort(a, a + n);
	for (int i = 0; i < n - 1; ++i)
    {
		if (a[i] == a[i + 1])
        {
			puts("NO");
			return 0;
        }
    }
	puts("YES");
	return 0;
}


Measured memory_bytes: 896
S=input()
flg=0
for i in range(len(S)):
  if(i%2==0):
    if(S[i]=="L"):
      print("No")
      flg=1
      break
  else:
    if(S[i]=="R"):
      print("No")
      flg=1
      break
if(flg==0):
  print("Yes")
      

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < int(n); i++)
#define rep1(i,n) for (int i = 1; i <= int(n); i++)
#define repR(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep1R(i,n) for (int i = int(n); i >= 1; i--)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define cauto const auto
#ifdef LOCAL
#define dump(...) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] ", _dmp_(#__VA_ARGS__, __VA_ARGS__);
void _dmp_(const char*) { cerr << endl; }
template <class T, class... U>
void _dmp_(const char *s, T const& x, U const& ...y) { const char *o = "({[", *e = "]})"; for (int i = 0; *s != '\0'; cerr << *s++) { if (count(o,o+3,*s)) i++; if (count(e,e+3,*s)) i--; if (!i && *s == ',') break; } cerr << " = " << x; if (*s == ',') cerr << ", ", s++; _dmp_(s, y...); }
#else
#define dump(...)
#endif
using ll = long long;
#define int ll
template <class T> using pque_max = priority_queue<T>;
template <class T> using pque_min = priority_queue<T, vector<T>, greater<T> >;
#define CONAINER_OUTPUT os << "{"; for (auto const& x : v) os << " " << x; return os << " }";
template <class T> ostream& operator<<(ostream& os, vector<T> const& v) { CONAINER_OUTPUT }
template <class T> ostream& operator<<(ostream& os, deque<T> const& v) { CONAINER_OUTPUT }
template <class T> ostream& operator<<(ostream& os, set<T> const& v) { CONAINER_OUTPUT }
template <class T, class U> ostream& operator<<(ostream& os, map<T,U> const& v) { CONAINER_OUTPUT }
#undef CONAINER_OUTPUT
template <class T> istream& operator>>(istream& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }
template <class T, class S> ostream& operator<<(ostream& os, pair<T,S> const& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <class T, class S> istream& operator>>(istream& is, pair<T,S> const& p) { return is >> p.first >> p.second; }
struct _Init_ { _Init_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); } } _init_;

template <class T> void quit(T const& x) { cout << x << endl; exit(0); }
template <class T> bool chmin(T& x, T const& y) { if (x > y) { x = y; return true; } return false; }
template <class T> bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; }
template <class It> auto sumof(It b, It e) { return accumulate(b,e,typename iterator_traits<It>::value_type{}); }
#define YesNo(c) ((c) ? "Yes" : "No")
////////////////////////////////

int32_t main() {
    int a,b; cin >> a >> b;
    int g = __gcd(a,b);
    int c = 0;
    for (int i = 2; i*i <= g; i++) {
        if (g%i == 0) {
            c++;
            while (g%i == 0) g /= i;
        }
    }
    if (g != 1) c++;
    cout << c+1 << endl;
}


Measured memory_bytes: 256
from sys import stdin
from decimal import Decimal, ROUND_HALF_UP

n = int(stdin.readline().rstrip())
data = list(map(int, stdin.readline().rstrip().split()))
p = sum(data) / n

#p should be int
p_int = (Decimal(p).quantize(Decimal('1'), ROUND_HALF_UP))

Sum = 0
for i in data:
	Sum  += (i - p_int) ** 2 
print(Sum)

Measured memory_bytes: 9956
#include <stdio.h>
#include <cstring>
#include <algorithm>

using std::max;

int row, col;
int flag[1002][1002];
int mons[2][2];

int node(char c)
{
	if (c == 'J')return 0;
	if (c == 'O')return 1;
	return 2;
}

int isap(int a,int b,int c,int d)
{
	return (a == mons[0][0] && b == mons[0][1] && c == mons[1][0] && d == mons[1][1]) ? 1 : 0;
}
#define isap_(fl,i,j) isap(fl[i][j],fl[i][j+1],fl[i+1][j],fl[i+1][j+1])

int main(void)
{
	scanf("%d %d", &row, &col);
	memset(flag, 0xFF, sizeof(flag));
	for (int i = 1; i <= row; ++i)
	{
		char tmp[1001]; scanf("%s", tmp);
		for (int j = 0; j < col; ++j)
		{
			flag[i][j+1] = node(tmp[j]);
		}
	}
	char tmp[3];
	scanf("%s", tmp);
	mons[0][0] = node(tmp[0]);
	mons[0][1] = node(tmp[1]);
	scanf("%s", tmp);
	mons[1][0] = node(tmp[0]);
	mons[1][1] = node(tmp[1]);
	int answer = 0;
	for (int i = 1; i < row; ++i)
	{
		for (int j = 1; j < col; ++j)
		{
			if (isap_(flag,i,j))
			{
				++answer;
			}
		}
	}
	int maxrem = 0;
	for (int i = 1; i <= row; ++i)
	{
		for (int j = 1; j <= col; ++j)
		{
			if (i == 4 && j == 4)
			{
				int a = 3;
			}
			int rem = isap_(flag,i-1,j-1) + isap_(flag,i-1,j) + isap_(flag,i,j-1) + isap_(flag,i,j);
			int flij = flag[i][j];
			int maxr = 0;
			for (int k = 0; k <= 2; ++k)
			{
				flag[i][j] = k;
				maxr = max(maxr, isap_(flag, i - 1, j - 1) + isap_(flag, i - 1, j) + isap_(flag, i, j - 1) + isap_(flag, i, j));
			}
			flag[i][j] = flij;
			maxrem = max(maxrem, maxr - rem);
		}
	}
	printf("%d\n",answer + maxrem);
	return 0;
}

Measured memory_bytes: 6664
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

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

    int ans = 0;
    vector<int> cnt(n + 1, 0);
    rep(i, n){
        int a;
        cin >> a;
        if(a > n) ans++;
        else cnt[a]++;
    }
    for(int i = 1; i <= n; i++){
        if(cnt[i] > i) ans += cnt[i] - i;
        else if(cnt[i] < i) ans += cnt[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
  size_t N;
  scanf("%zu", &N);

  std::vector<size_t> p(N);
  for (size_t i=0; i<N; ++i)
    scanf("%zu", &p[i]);

  int res=0;
  for (size_t i=0; i+1<N; ++i)
    if (p[i] == i+1) {
      ++res;
      std::swap(p[i], p[i+1]);
    }

  if (p[N-1] == N)
    ++res;

  printf("%d\n", res);
}


Measured memory_bytes: 1024
//PCK2015予選4
#include<iostream>
using namespace std;

int main(){
    int t[4] = {6,4,3,2};
    for(int i=0;i<4;++i){
        int n,m;
        cin>>n>>m;
        cout<<t[n-1]*m*1000<<endl;
    }
}



Measured memory_bytes: 3056
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long
const int MOD=1e9+7;
const int INF=1e15;
const double pi=acos(-1.0);

signed main(){
    int W,H,N;cin>>W>>H>>N;
    int lmax=0,rmin=W,umin=H,smax=0;
    REP(i,N){
        int x,y,a;cin>>x>>y>>a;
        if(a==1)lmax=max(lmax,x);
        if(a==2)rmin=min(rmin,x);
        if(a==3)smax=max(smax,y);
        if(a==4)umin=min(umin,y);
    }
    int d=max(0ll,umin-smax);
    int z=max(0ll,rmin-lmax);
    cout<<d*z<<endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

# D - Brick Break
n = int(input())
a = list(map(int, input().split()))
i = 1
bricks = 0

for ai in a:
	if ai == i:
		bricks += 1
		i += 1

if bricks == 0:
	print(-1)
else:
	print(n - bricks)

Measured memory_bytes: 25912
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
void Say(bool say, string a = "Yes", string b = "No"){cout << (say ? a : b) << endl;};

double dp[3030][3030];

int main(){

    ll N;
    cin >> N;
    dp[0][0] = 1;
    for(ll i = 0; i < N; i++){
        double p;
        cin >> p;
        for(ll j = 0; j < N; j++){
            dp[i + 1][j] += (1 - p) * dp[i][j];
            dp[i + 1][j + 1] += p * dp[i][j];
        }
    }
    double ans = 0;
    for(ll i = 0; i <= N; i++){
        if(i * 2 >= N)ans += dp[N][i];
    }
    printf("%.9f\n", ans);

    return 0;
}

Measured memory_bytes: 71936
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
int main(){
string s,t;cin>>s>>t;
int a,b;cin>>a>>b;
string u;cin>>u;

if(u==s)cout<<a-1<<" "<<b<<endl;
else cout<<a<<" "<<b-1<<endl;

}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

const long long MAX = 2000000000000000;

int main()
{
    long long t1, t2, a1, a2, b1, b2;
    cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;

    long long d2 = (b1 * t1 + b2 * t2) - (a1 * t1 + a2 * t2);
    if(d2 == 0){
        cout << "infinity" << endl;
        return 0;
    }
    else if(d2 < 0){
        swap(a1, b1);
        swap(a2, b2);
        d2 *= -1;
    }

    long long d1 = a1 * t1 - b1 * t1;
    if(d1 < 0){
        cout << 0 << endl;
        return 0;
    }

    long long ans = (d1 + d2 - 1) / d2 * 2 - 1;
    if(d1 % d2 == 0)
        ++ ans;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;

#define EPS 1e-10

int main(){

	int n;
	cin >> n;
	while(n--){
		double x1, x2,x3,x4,y1,y2,y3,y4;
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
		double cross = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
		if(fabs(cross) < EPS) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3212
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
using namespace std;
#define dump(x) cout << (x) << '\n';
typedef int64_t Int;
Int mod = 1e9 + 7;
Int INF = 1e9 + 7;

//vector<pair<int, int>> v[19803];

int main() {
	vector<pair<int, int>> v;
	while (true) {
		int h, w;
		cin >> h >> w;
		if (h == 0) break;
		int n = h * h + w * w;
		int mi = 1e9;
		pair<int, int> p;
		for (Int i = 1; i <=150; i++) {
			for (Int j = i+1; j <=150; j++) {
				int x = i * i + j * j;
				if (x > n && mi > x) {
					mi = x;
					p = { i, j };
				}
				else if (x == n && h < i) {
					p={ i,j };
					goto PUSHBACK;
				}
			}
		}
		PUSHBACK:
		v.emplace_back(p);
	}
	for (auto x : v) cout << x.first << " " << x.second << endl;
	return 0;
}


Measured memory_bytes: 3024
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{   
    int n,k;
    cin >> n >> k;
    map<int,int> balls;
    rep(i,n)
    {
        int ai;
        cin >> ai;
        if(balls.count(ai)>0)
            balls[ai]++;
        else
            balls[ai] = 1;
    }

    priority_queue<int,vector<int>,greater<int>> pq;
    for(auto& b:balls)
        pq.push(b.second);
    
    int m = pq.size();
    int cnt = 0;
    for(int i=0;i<m-k;++i)
    {
        cnt += pq.top();
        pq.pop();
    }
    
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 10748
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int,int> pii;
typedef pair <db,db> pdd;
typedef vector<int> vi;
//typedef vector<vector<int> > matrix;
 
#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))
 
#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
 
inline int gcd(int a,int b){if(a==0) return b;return gcd(b%a,a);}
inline int power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const double EPS = 1e-9;
const ll MOD=998244353;
const ll hell=1000000007;
const int INF = 1e16;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);
 
double startTime;
double getCurrentTime() {
    return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
 
const int N=200005;

int st[4*N+1];int lazy[4*N];
int dp[N+1][2];
void update(int i,int l,int r,int qs,int qe,int x)
{
if(lazy[i])
{
    st[i]+=lazy[i];
    if(l!=r)
    {
        lazy[2*i+1]+=lazy[i];
        lazy[2*i+2]+=lazy[i];
    }
    lazy[i]=0;
}
if(qs>r||qe<l)
return;
if(qs<=l&&qe>=r)
{
    st[i]+=x;
    if(l!=r)
    {
        lazy[2*i+1]+=x;
        lazy[2*i+2]+=x;
    }
    lazy[i]=0;
    return;
}
int m=(l+r)/2;
update(2*i+1,l,m,qs,qe,x);
update(2*i+2,m+1,r,qs,qe,x);
st[i]=max(st[2*i+1],st[2*i+2]);
}
int query(int i,int l,int r,int qs,int qe)
{
if(lazy[i])
{
    st[i]+=lazy[i];
    if(l!=r)
    {
        lazy[2*i+1]+=lazy[i];
        lazy[2*i+2]+=lazy[i];
    }
    lazy[i]=0;
}
if(qs>r||qe<l)
return -INF;
if(qs<=l&&qe>=r)
{
    return st[i];
}
int m=(l+r)/2;
return max(query(2*i+1,l,m,qs,qe),query(2*i+2,m+1,r,qs,qe));

}


void solve()
{
for(int i=0;i<4*N;i++)
st[i]= -INF;
int n,m;
cin>>n>>m;
vector<pair<int,int>> qr[n+1];
int l,r,a;
int sm[n+1]={0};
for(int i=0;i<m;i++)
{
    cin>>l>>r>>a;
    qr[r].pb(m1(l,a));
    sm[r]+=a;
}
update(0,0,n,0,0,INF);
for(int i=1;i<=n;i++)
{
    dp[i][1]=sm[i]+max(dp[i-1][0],dp[i-1][1]);
    for(int j=0;j<qr[i].size();j++)
    {
       l=qr[i][j].fi;
       if(l<i)
       update(0,0,n,l,i-1,qr[i][j].se);
    }
    dp[i][0]=query(0,0,n,0,i-1);
    update(0,0,n,i,i,dp[i][1]+INF);

}
cout<<max(dp[n][0],dp[n][1])<<endl;




}

int32_t main()
{
    //IOS;
    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        
        solve();
    }
    return 0;
}


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

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 5, base = 1e9 + 7;

int f[maxn];
int n;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  f[0] = 0;
  f[1] = n;
  f[2] = 1ll * n * n % base;
  int sum = 0;
  for (int i = 3; i <= n; i++) {
    f[i] = (f[i - 1] + 1ll * (n - 1) * (n - 1) % base) % base;
    f[i] = (f[i] + sum + n - i + 2) % base;
    sum = (sum + f[i - 2]) % base;
  }
  cout << f[n] << '\n';
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+5;
const ll mod =   1e9+7;
ll ans=0;ll n;
int main()
{  fast
  cin>>n;
  for(ll i=1;i<=n;i++){
  	ll x=(i*(i+1)/2ll);
	ans=(ans+x);
  }//cout<<ans<<endl;
  for(int i=1;i<n;i++){
  	ll x, y;
  	cin>>x>>y;
	if(x>y)
	swap(x,y);
	ll xx=(x*(n-y+1));//cout<<x<<" "<<(n-y+1)<<endl;
	ans=(ans-xx);
  }

cout<<ans;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007LL
#define eps 1e-13
#define PI 3.141592653589793238L
#define INF 1000000011
#define INFLL 1000000000000000011LL
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define mp make_pair
#define F first
#define S second
#define pb(x) push_back(x)
#define fo(i,a,n) for(i = (a); i < (n); i++)
#define gtl(x) getline(cin, (x))
#define flsh fflush(stdout)
#define sws ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define io_file freopen("/usr/local/google/home/absajwan/input_file.in", "r", stdin); freopen("/usr/local/google/home/absajwan/output_file.out", "w", stdout)

ll modx(ll Base, ll exponent)
{
	ll ans = 1;
	if(Base == 1)
		return Base;
	while(exponent)
	{
		if(exponent & 1)
			ans = (ans * Base)%mod;
		Base = (Base * Base)%mod;
		exponent = exponent >> 1;
	}
	return ans;
}

ll inmodx(ll num)
{
	return (modx(num, mod-2LL));
}

bool cmp(pll a, pll b)//true for a before b
{
	return ((a.S*b.F) <= (b.S*a.F));
}

const int N = (2e5) + 9;
const int M = (N<<2) + 9;
const int LOGN = ((int)log2(N)) + 3;
const int LOGM = ((int)log2(M)) + 3;
const int BUCK = 650;

ll a[N], pre_sum[N], pre_xor[N];

ll sum(int l, int r)
{
	if(l > r)
		return 0LL;
	return (pre_sum[r]-pre_sum[l-1]);
}

ll xor_(int l, int r)
{
	if(l > r)
		return 0LL;
	return (pre_xor[r]^pre_xor[l-1]);
}

int binsea(int l, int r, int z)
{
	if(l > r)
		return z;
	int mid = (l+r)>>1;
	if(sum(z+1,mid) == xor_(z+1,mid))
		return max(mid, binsea(mid+1,r,z));
	return binsea(l,mid-1,z);
}

void solve()
{
	int n, i, j, k, val;
	ll ans = 0LL;
	cin >> n;
	fo(i,1,n+1)
		cin >> a[i];
	fo(i,1,n+1)
	{
		pre_xor[i] = pre_xor[i-1]^a[i];
		pre_sum[i] = pre_sum[i-1]+a[i];
	}
	fo(i,1,n+1)
		ans += 1LL*(binsea(i,n,i-1)-i+1);
	cout << ans << '\n';
	return;
}

int main()
{
	sws;
	// clock_t clk;
	// clk = clock();
	// io_file;
	// srand (time(NULL));

	//Code here

	int t = 1, cs;
	// cout << fixed << setprecision(9);
	// cin >> t;
	fo(cs,1,t+1)
	{
		// cout << "Case #" << cs << ": ";
		solve();
	}

	// Code ends here

	// clk = clock() - clk;
	// cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
	return 0;
}


Measured memory_bytes: 4992
n,k=map(int,input().split())
A=[int(input()) for i in range(n)]

def track_num(n):
    cnt,track=0,1
    for i in A:
        if cnt+i>n:
            track +=1
            cnt=i
        else:
            cnt +=i
    return track

def Binaryserch():
    left,right=max(A),sum(A)+1
    ans=0
    while left<right:
        mid=(left+right)//2
        track=track_num(mid)
        if track<=k:
            ans=mid
            right=mid
        elif track>k:
            left=mid+1
    return ans

print(Binaryserch())


Measured memory_bytes: 9580
#include <queue>
#include <iostream>

using namespace std;
int main() {
  int num;
  int quantum;
  int count = 0;

  cin >> num >> quantum;

  queue<pair <string,int> > Q; // pairを格納するキュー

  string word;
  int time;
  int anstime = 0;
  while (count != num){
    cin >>word >> time;
    Q.push(pair<string,int>(word,time));
    count++;
  }

  while (! Q.empty()) {

  pair<string, int> top = Q.front(); // 要素がある間
  string tp = top.first;
  int n = top.second;
  if (n <= quantum){
     Q.pop(); // 先頭要素を廃棄
     anstime = anstime + top.second;
     cout << top.first << ' ' << anstime << endl;
   }
   else {
     anstime = anstime + quantum;
     Q.pop();
     Q.push(pair<string,int>(top.first,top.second-quantum));
   }

  }
  
}



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

using namespace std;
#define rep(i, N) for(int i=0;i<int(N);++i)
#define rep1(i, N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

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

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

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

const int INF = (ll) 1e9;
const ll INFLL = (ll) 1e18 + 1;
const ll MOD = (ll) 1e9 + 7;
const double PI = acos(-1.0);

/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll N, K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i,N){
        cin >> A[i];
        A[i]--;
    }
    vector<bool> used(N, false);
    deque<int> mv;
    int cur = 0;
    while(1){
        used[cur] = true;
        mv.push_back(cur+1);
        int nx = A[cur];
        if(used[nx]){
            mv.push_back(nx+1);
            break;
        }
        cur = nx;
    }
    if(K < (ll)mv.size()){
        cout << mv[K] << endl;
        return 0;
    }
    while(true){
        if(mv.front() == mv.back()){
            mv.pop_front();
            K--;
            break;
        }
        else{
            K--;
            mv.pop_front();
        }
    }
    int sz = mv.size();
    cout << mv[K%sz] << endl;
}

Measured memory_bytes: 4828
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <math.h>
#include <set>
#include <fstream>
using namespace std;

int main()
{
	int N;
	string S;
	cin>>N>>S;
	int R=0;
	int B=0;

	for(int i=0; i<S.size(); i++)
	{
		if(S[i]=='R')
		{
			R++;
		}
		else
		{
			B++;
		}
	}
	if(R>B)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int m1, m2;
int d1, d2;
int main() {
    cin >> m1 >> d1;
    cin >> m2 >> d2;
    if(m1 != m2) {
        cout << 1 << endl;
    }else {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

// Split
namespace util {

std::vector< std::string > split(std::string s, char delimiter)
{
  std::vector< std::string > vs;
  std::string sub;
  for (auto c : s) {
    if (c == delimiter) vs.push_back(sub), sub.clear();
    else sub += c;
  }
  vs.push_back(sub);
  return vs;
}

} // namespace util

// Minimum, Maximum
template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }
template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

// Output
template<class T, class S> std::ostream& operator << (std::ostream& os, std::pair<T, S> p)
{
  return os << "(" << p.first << " " << p.second << ")";
}

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  for (ll i = 0; i < (ll)v.size(); i++){ os << " [" << i << "]" << v[i]; if (i % 10 == 9) os << std::endl; }
  //os << v[0]; for (ll i = 1; i < (ll)v.size(); i++){ os << " " << v[i]; }
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::map< T, S > m)
{
  ll i = 0; for (auto p : m){ os << " [" << i << "]" << p.first << "->" << p.second; i++;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  ll N, A, B;
  std::cin >> N >> A >> B;

  ll ans = std::min(N*A, B);
  print(ans);

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<bool> p(55556,true);
  p[0]=false;
  p[1]=false;
  vector<int> a;
  for(int i=2;i<=55555;i++){
    if(p[i]){
      if(i%5==1){
        a.push_back(i);
      }
      for(int j=2;i*j<=55555;j++){
        p[i*j]=false;
      }
    }
  }
  for(int i=0;i<n;i++){
    cout << a[i] << " ";
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
char m[8][9];
int f(int x,int y){
  if(m[y][x]=='1'){
    m[y][x]='0';
    for(int i=-3;i<4;++i){
      if(x+i<8&&x+i>=0) f(x+i,y);
      if(y+i<8&&y+i>=0) f(x,y+i);
    }
  }
}

int main(){
  int n,x,y;
  cin>>n;
  for(int j=1;j<=n;++j){
    for(int i=0;i<8;++i) cin>>m[i];
    cin>>x>>y;--x;--y;
    f(x,y);
    cout<<"Data "<<j<<":"<<endl;
    for(int i=0;i<8;++i) cout<<m[i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 1164
icase=0
if icase==0:
    from fractions import gcd
#    from math import gcd

    def cd2(nn):
        nnn=int(nn**0.5)+1
        cdl=set()
        for i in range(1,nnn):
            if nn%i==0:
                r=nn//i
                if not i in cdl:
                    cdl.add(i)
                if not r in cdl:
                    cdl.add(r)
        return list(cdl)            

    a,b,k=map(int,input().split())
    ki=gcd(a,b)
    kilist=cd2(ki)
    kilist.sort(reverse=True)
    print(kilist[k-1])

Measured memory_bytes: 5076
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, m; cin >> n >> m;
	vi ans(n);
	REP(i, m)
	{
		int a, b; cin >> a >> b;
		ans[a - 1]++;
		ans[b - 1]++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
/**
	* Author   : Sriram M
	* Date     : 
	* Semester : 5
	* SSN College of Engineering Chennai
    Aug Challenge
**/

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    #ifndef ONLINE_JUDGE 
  
        // For getting input from input.txt file 
        freopen("input.txt", "r", stdin); 
      
        // Printing the Output to output.txt file 
        freopen("output.txt", "w", stdout); 
      
    #endif

    long n;
    cin >> n;
    long long h;
    long long ans = 0;
    long long max = -1;

    while(cin >> h) {
        if(h >= max) {
            max = h;
            continue;
        }
        else {
            ans += max - h;
        }

    }

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


Measured memory_bytes: 3588
from collections import defaultdict

############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
X,Y,a,b,c = invr()
red = inlt() ; red.sort(reverse = True)
green = inlt(); green.sort(reverse = True)
colorless = inlt(); colorless.sort(reverse = True)

red = red[:X]
green = green[:Y]

red.reverse()
green.reverse()

r_index = 0
g_index = 0
c_index = 0
while True:
    if r_index >= len(red) or g_index >= len(green) or c_index >= len(colorless):
        break
    if red[r_index] > green[g_index]:
        if colorless[c_index] > green[g_index]:
            green[g_index] = colorless[c_index]
            g_index += 1
            c_index += 1
        else:
            break
    else:
        if colorless[c_index] > red[r_index]:
            red[r_index] = colorless[c_index]
            r_index += 1
            c_index += 1
        else:
            break

if r_index < len(red):
    if c_index < len(colorless):
        while r_index < len(red) and c_index < len(colorless):
            if red[r_index] < colorless[c_index]:
                red[r_index] = colorless[c_index]
                r_index+= 1
                c_index += 1
            else:
                break

if g_index < len(green):
    if c_index < len(colorless):
        while g_index < len(green) and c_index < len(colorless):
            if green[g_index] < colorless[c_index]:
                green[g_index] = colorless[c_index]
                g_index+= 1
                c_index += 1
            else:
                break

print(sum(red) + sum(green))
            


Measured memory_bytes: 24488
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#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 all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;
const bool DEBUG = false;

#define MAX 10010
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end())
signed main() {
	for (int n; cin >> n&&n;) {
		vector<int> cnt((n - 1) / 2 + 1, 0);
		vector<int> v;
		rep(i, 1, n) {
			v.emplace_back((i*i) % n);
		}
		sort(all(v));
		UNIQUE(v);
		dumpc(v);
		rep(i, 0, v.size())rep(j, 0, v.size()) {
			if (v[i] == v[j])continue;
			int diff = v[i] - v[j];
			if (diff < 0)diff += n;
			if (diff > (n - 1) / 2.0)diff = n - diff;
			dump(diff);
			dump(cnt.size());
			cnt[diff]++;
		}
		dumpc(cnt);
		rep(i, 1, (n - 1) / 2 + 1)cout << cnt[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3280
#include<bits/stdc++.h> 
using namespace std;
int a[100010]={0};
int ans[100010]={0};
int knot[50001]={0};
int p=0;
int find(int x)
{
	int now=knot[x];
	ans[now]++;
	ans[now+1]++;
	int place=now-1;
	int radd=0,ladd=0;
	while(a[place]==1)
	{
		int mv=now-place;
		if(mv%2==1)	ladd++;
		else	radd++;
		place--;
	}
	ans[now]+=radd;
	ans[now+1]+=ladd;
	radd=0,ladd=0;
	place=now+2;
	while(a[place]==-1)
	{
		int mv=place-now;
		if(mv%2==0)		radd++;
		else	ladd++;
		place++;
	}
	ans[now]+=radd;
	ans[now+1]+=ladd;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
    	if(s[i]=='R')	a[i+1]=1;
    	if(s[i]=='L')
		{
    		a[i+1]=-1;	
    		if(s[i-1]=='R')	knot[++p]=i;
		}
    	
	}
	for(int i=1;i<=p;i++)
	{
		find(i);
		//cout<<knot[i]<<endl;
	}
	/*for(int i=1;i<=s.size();i++)
	{
		cout<<a[i];
	}*/
	for(int i=1;i<=s.size();i++)
	{
		cout<<ans[i]<<" ";
	}
	//cout<<endl;
	//cout<<knot[1]<<endl<<knot[2]<<endl<<knot[3];
    return 0;   
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int a, b,c;
  cin >> a >> b >> c;
  cout << a+b+c-max({a,b,c}) << endl;
}

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

int main() {
	int h, w;
	cin >> h >> w;

	vector<string> g(h);
	for (int i = 0; i < h; i++) {
		cin >> g[i];
	}

	vector<string> a(h, string(w, '.'));
	vector<string> b(h, string(w, '.'));
	for (int i = 1; i < h - 1; i++) {
		for (int j = 1; j < w - 1; j++) {
			if (i == 1) {
				a[i][j] = '#';
			} else {
				if (j % 2 == 1) {
					a[i][j] = '#';
				}
			}
		}
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			b[i][j] = a[i][j] == '#' ? '.' : '#';
		}
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (g[i][j] == '#') {
				a[i][j] = b[i][j] = '#';
			}
		}
	}

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

	cout << endl;

	for (int i = 0; i < h; i++) {
		cout << b[i] << endl;
	}
}

Measured memory_bytes: 1536
// This is the start of  template//
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long int
#define ll int 
#define vll vector<int>
#define pb push_back
#define pll pair<int,int>
#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
void input(){
#ifndef ONLINE_JUDGE 
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout); 
#endif
}
#define INF LONG_LONG_MAX
#define mod 1000000007
#define array(a,n) vll a(n); rep(i,0,n) cin>>a[i];
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define cases int t; cin>>t; while(t--)
#define printall(a) rep(i,0,a.size()) cout<<a[i]<<" "; cout<<endl;
ll power(ll a,ll n)
{
	if(n==0)
		return 1;
	if(n%2)
	{
		return (a*power((a*a)%mod,n/2))%mod;
	}
	return power((a*a)%mod,n/2);
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
// input();
  int n,total = 0 ,total2 = 0 ,final = 0; 
  cin>>n;
  array(a,n);
  for(int i = 0 ;i<n ;i++)
  {
  	total += a[i];
  	total %= mod;

  	total2 += power(a[i],2);
  	total2 %= mod;
  }
  // cout<<total2<<" ";
  total2 = (power(total,2) - total2 + mod)%mod;

  final = (total2%mod*power(2,mod-2)%mod)%mod;
  cout<<final;

}



Measured memory_bytes: 4776
//***Little by little one travels far***
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main()
{
    ll n,f=0;
    cin>>n;

    string s;
    cin>>s;

    if(n%2!=0){
        cout<<"No";
        return 0;
    }

    for(ll i=0;i<(n/2);i++){
        if(s[i]!=s[i+(n/2)]){
            f=1;
            break;
        }
    }
    if(f==1) cout<<"No";
    else cout<<"Yes";
}

Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
for(var i=0;i<Arr.length;i++){
   if(Arr[i]=="0")break;
   var arr=Arr[i].split(" ").map(Number);
   if(arr.length==1)continue;
   var ave=(arr[0]+arr[1]+arr[2])/3;
   var str="C";
   if(arr.indexOf(100)!=-1){str="A";}
   else if((arr[0]+arr[1])/2>=90){str="A";}
   else if(ave>=80){str="A";}
   else if(ave>=70){str="B";}
   else if(ave>=50 && (arr[0]>=80 || arr[1]>=80)){str="B";}
   console.log(str);
}

Measured memory_bytes: 10876
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int k;
  cin >> k;
  int n=s.size();
  for(int i=0;i<n;i++){
    if(s[i]=='a'){
      continue;
    }
    if('z'-s[i]<=k-1){
      k-='z'-s[i]+1;
      s[i]='a';
    }
  }
  if(k!=0){
    s[n-1]+=k%26;
  }
  cout << s << endl;
}

Measured memory_bytes: 640
fun main() {
    println(solve())
}

val solve: () -> Any = {
    val (N,K) = readIntList()
    val set = (1..N).toList().toMutableSet()
    repeat(K) {
        val d = readInt()
        val A = readIntList()
        set -= A
    }
    set.size
}

val mod: Int = 1_000_000_007

fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

fun <T> T.alsoPrintln() = also { println(this) }

fun Boolean.toYesOrNo(yes: String = "Yes", no: String = "No") = if (this) yes else no

Measured memory_bytes: 39540
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
using namespace std;
bool find(string s,string f){
	REP(i,s.size())
		REP(j,f.size())
			if(i+j>=s.size() || s[i+j]!=f[j])
			break;
			else if(j==f.size()-1)
			return true;
	return false;
}

int main() {
	string books[101][3],query[4];
	int N,Q;
	cin >> N ;
	REP(i,N)
		REP(j,3)
			cin >> books[i][j];
	cin >> Q;
	REP(i,Q){
		REP(j,4)
			cin >> query[j];
		REP(j,N){
			bool ans=true;
			REP(k,4){
				if(query[k]=="*")
				continue;
				if(k<=1)
					if(!find(books[j][k],query[k]))
					ans=false;
				if(k==2)
					if(!(query[k]<=books[j][2]))
					ans=false;
				if(k==3)
					if(!(query[k]>=books[j][2]))
					ans=false;
			}
			if(ans)
			cout << books[j][0] << endl;
		}
		if(i!=Q-1)
		cout << endl;
	}

	// your code goes here
	return 0;
}

Measured memory_bytes: 1240
#include "bits/stdc++.h"
using namespace std ;

long long p[100005] , q[100005] , r[100005] ; 

int main(){
    int x , y , a , b , c ;
    cin >> x >> y >> a >> b >> c ;
    for( int i = 0 ; i < a ; i++ ){
        cin >> p[i] ;
    }
    for( int i = 0 ; i < b ; i++ ){
        cin >> q[i] ;
    }
    for( int i = 0 ; i < c ; i++ ){
        cin >> r[i] ;
    }
    sort(p,p+a);
    sort(q,q+b);
    sort(r,r+c);
    int A = a- x ;
    int B = b - y ;
    int i = A  , j = B , k = c-1 ;
    while( i < a && j < b && k >= 0  ){
        if( r[k] <= min(p[i],q[j])) break ;
        else{
            if( p[i] <= q[j] ){
                p[i] = r[k] ;
                k-- ;
                i++ ;
            }
            else{
                q[j] = r[k];
                k-- ;
                j++ ;
            }
        }
    }
    while( i < a && k >= 0 ){
        if(  r[k] <= p[i] ) break ;
        else{
            p[i] = r[k] ;
            k-- ;
            i++ ;
        }
    }
    while( j < b && k >= 0 ){
        if(  r[k] <= q[j] ) break ;
        else{
            q[j] = r[k] ;
            k-- ;
            j++ ;
        }
    }
    long long ans = 0 ;
    for( i = A ; i < a ; i++ ){
        ans += p[i] ;
    }
    for( i = B ; i < b ; i++ ){
        ans += q[i] ;
    }
    cout << ans << endl ;
    
    return 0 ;
}

Measured memory_bytes: 2560
N,K = map(int,input().split())
list1 ={i for i in range(1,N+1)}
list2 = set()
for i in range(K):
  NN = int(input())
  MM = map(int,input().split())
  for j in MM:
    list2.add(j)

ans = list1 -list2
print(len(ans))

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

// 素因数分解
vector<pair<long long, long long>> prime_factorization(long long n)
{
    vector<pair<long long, long long>> res;

    for (long long i = 2; i * i < n; i++)
    {
        int cnt = 0;
        while (n % i == 0)
        {
            cnt++;
            n /= i;
        }
        res.push_back(make_pair(i, cnt));
    }

    if (n != 1)
    {
        res.push_back(make_pair(n, 1));
    }
    return res;
}

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

    ll N;
    cin >> N;

    vector<pair<ll, ll>> p_res = prime_factorization(N);

    ll l = p_res.size();
    ll all_cnt = 0;
    for (int i = 0; i < l; i++)
    {
        pair<ll, ll> p = p_res[i];

        ll e = p.second;

        ll j = 1;
        ll cnt = 0;
        while (e - j >= 0)
        {
            e -= j;
            j++;
            cnt++;
        }

        all_cnt += cnt;
    }

    cout << all_cnt << endl;

    return 0;
}


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

int main() {
	int N, K, S, a = 1;
	cin >> N >> K >> S;
	for (int i = 0; i < K; i++) cout << S << ' ';
	if (S != 1000000000) a = S + 1;
	for (int i = 0; i < N - K; i++) cout << a << ' ';
}

Measured memory_bytes: 1280
#include <stdio.h>
int main(void){
  int n, i;
  long long int a[100005], ans = 1, b = 1, sum = 0;
  scanf("%d", &n);
  
  for (i = 0; i <= n; i++)
  {
      scanf("%lld", a + i);
        sum += a[i];
  }
  
  if (n == 0)
  {
      if (a[0] == 1)
        printf("1");
      else
        printf("-1");
    return (0);
  }
  
  
  
  
  
    for (i = 1; i <= n; i++)
    {
        if (2 * b < sum)
            b *= 2;
        else
            b = sum;
        
        ans += b;
        b -= a[i];
        sum -= a[i];

        if (b < 0)
        {
            printf("-1");
            return (0);
        }
    }
    if (b != 0)
    {
        printf("-1");
        return (0);
    }
    printf("%lld", ans);
   return (0);
}


Measured memory_bytes: 2512