akhauriyash/Code-Regression huggingface dataset:
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

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

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

ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}

ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}

//-----------------------ここから-----------

int main(void){
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> s(n), c(m);
    for(int i = 0; i < n; i++){
        cin >> s[i].first >> s[i].second;
    }    
    for(int i = 0; i < m; i++){
        cin >> c[i].first >> c[i].second;
    }
 
    for(int i = 0; i < n; i++){
        ll shortest = INF;
        int ans = 0;
        for(int j = 0; j < m; j++){
            ll tmp = abs(s[i].first - c[j].first) + abs(s[i].second - c[j].second);
            if(shortest > tmp){
                shortest = tmp;
                ans = j;
            }
        }
        cout << ans + 1 << endl;
    }
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    T = input().replace('?', 'D')
    print(T)







main()



Measured memory_bytes: 10136
#include<stdio.h>
#include<string.h>
#define LEN 50

int main(void){
  int n;
  char p[LEN];
  scanf("%d",&n);
  scanf("%s",p);

  int cnt=0,i;
  for(i=0;i<n;i++)
    if(p[i]=='A'&&p[i+1]=='B'&&p[i+2]=='C')
      cnt++;
  
  printf("%d\n",cnt);
  
  return 0;
}
  
  
  


Measured memory_bytes: 1736
import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split())

A = [int(i)*(-1) for i in input().split()]



# print(A)
# for i in range(M):
# 	max_index = A.index(max(A))
# 	A[max_index] = int(A[max_index]/2)

# print(sum(A))
heapq.heapify(A)

for i in range(M):
	

	min = heapq.heappop(A)
	# 最小値を削除と値を渡す
	# print(A)
	# print(min)

	heapq.heappush(A,int(min/2))
	# print(A)


print(sum(A)*(-1))



Measured memory_bytes: 68376
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int n,m,s[2003],t[2003],d[2003][2003];
bool db = 0;
int a(int u,int v){
	int res = (u + v)%mod;
	if(res < 0) res += mod;
	return res;
}
int dp(int u,int v){
	int &ans = d[u][v];
	if(ans != LONG_MIN) {
		return ans;
	}
	if(u == 0 || v == 0) return ans = 1;
	return ans = a(a(dp(u,v-1),dp(u-1,v)),-(s[u]!=t[v])*dp(u-1,v-1));
}
signed main(){
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++) cin >> s[i];
	for(int i = 1 ; i <= m ; i ++) cin >> t[i];
	for(int i = 0 ; i <= n ; i ++)
		for(int j = 0 ; j <= m ; j ++)
			d[i][j] = LONG_MIN;
	cout << dp(n,m);
	
}


Measured memory_bytes: 31744
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int main(){
	int N, M;
	cin >> N >> M;
	int i, j;
	vi A, B;
	for (i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		A.push_back(a);
		B.push_back(b);
	}
	vi R(N, 0);
	for (i = 0; i < M; i++){
		R[A[i] - 1]++;
		R[B[i] - 1]++;
	}
	for (i = 0; i < N; i++){
		cout << R[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
#define ios cin.tie(0); ios::sync_with_stdio(false)
#define FIX(a) cout << fixed << setprecision(a)
//manip
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power(T a, T b) {return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
template<typename T> T gcd(T a, T b) {if (b == 0) return a; return gcd(b, a % b);}
template<typename T> T lcm(T a, T b) {return a / gcd(max(a, b), min(a, b)) * b;} //先に割る!!
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define out(a) cout << a << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
//algorithm
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0
//bfs, not x, y, i, j
//not !(i % 2), i % 2 == 0
//minimal required terms
//cast caution
//look constraints always

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    //out(comb(3, 2));
    
    
    COMinit();
    
    int n, k; cin >> n >> k;
    
    ll ans = 0;
    out(n - k + 1);
    rep3(i, 2, k + 1) {
        //n+1箇所にi+1個の仕切り
        ans = COM(k - 1, i - 1) * (COM(n - k - 1, i) + COM(n - k - 1, i - 2) + 2 * COM(n - k - 1, i - 1));
        ans %= mod;
        out(ans);
        ans = 0;
    }
    
    
}

/*
 連続してるの圧縮して考えよう
 iに関して独立に考えていい
 
 i = 1
 n - k + 1
 
 
 i = 2
 b, r, b, r
 r, b, r, b
 
 i = 3
 b, r, b, r, b
 r, b, r, b, r
 
 
 i = 100
 b, r, b, r, b, r, ...
 
 10^9 + 7超える時点で再帰不能
 
 
 
 
 n個の玉並べる
 仕切りを入れる
 
 i = 1
 仕切り2つ
 
 違うは
 
 
 
 連続青を1まとめとする
 i = 2
 2箇所に分ける
 r, b, r, b, r
 端のr = 0も可
 
 i = 5
 r, b, r, b, r, b, r, b, r, b, r
 間のrは必ず1以上
 
 bに関してはすべて1個以上
 k個の間(k-1)i-1個選ぶ
 
 
 n - k個
 1. 両端ない
 2. 両端ある
 
 2. (n-k)個の間(n-k-1)i個選ぶ
 
 1. n-k個 間i-2箇所
 
 3. 片端
 n-k-1個からi-1個選ぶ
 */



Measured memory_bytes: 12160
import itertools
import math

N = int(input())
P = tuple(list(map(int, input().split())))
Q = tuple(list(map(int, input().split())))

a = 0
b = 0
count = 0
for i in itertools.permutations([i for i in range(1, N + 1)]):
    count += 1
    if i == P:
        a = count
    if i == Q:
        b = count

print(abs(a - b))


Measured memory_bytes: 3064
//大文字->小文字 tolower(),逆はtoupper()
//int a = stoi(c); 文字列をintへ
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//絶対値 abs()
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

// Nの桁数
ll dig(ll N) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= 10;
	}
	return dig;
}
// x,yの最大公約数
ll gcd(ll x, ll y) {
	ll r;
	while (x%y) {
		r = x % y;
		x = y;
		y = r;
	}
	return y;
}

int main() {
	string S, T, U; cin >> S >> T >> U;
	string ans = "A";
	ans += T[0];
	ans += 'C';
	cout << ans << endl;
}

Measured memory_bytes: 256
a,b,c,d = map(int,input().split( ))


divc = b//c-(a-1)//c
divd = b//d-(a-1)//d

def gcd(s,t):
    while s%t!=0:
        tmp1 = s//t
        tmp2 = t
        t = s-tmp1*t
        s = tmp2
        #print(s,t)
    return t
g = gcd(c,d)
#print(g)
l = c*d//g
#print(l)
divl = b//l-(a-1)//l

ans = b-a+1 -divc-divd + divl

print(ans)




Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>


using namespace std;

void paint(vector<vector<int>> &area, int x, int y, int a) {

    for(int k = 0; k < area.size(); k++) {
        vector<int> row = area[k];

        // x < xi
        if(a == 1) {
            for(int i = 0; i < x; i++) {
                row[i] = 1;
            }
        }
        // x > xi
        if(a == 2) {
            for(int i = x; i < row.size(); i++) {
                row[i] = 1;
            }
        }
        area[k] = row;
    }

    if(a == 3) {
        for (int i = 0; i < y; i++) {
            vector<int> row = area[i];

            for(int j = 0; j < row.size(); j++) {
                row[j] = 1;
            }
            area[i] = row;
        }
    }
    if(a == 4) {
        for (int i = y; i < area.size(); i++) {
            vector<int> row = area[i];

            for(int j = 0; j < row.size(); j++) {
                row[j] = 1;
            }
            area[i] = row;
        }
    }

}

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

    vector<int> blank;
    for(int i = 0; i < w; i++) {
        blank.push_back(0);
    }

    vector<vector<int>> table, area;
    for(int i = 0; i < h; i++) {
        area.push_back(blank);
    }

    for(int i = 0; i < n; i++) {
        int x,y,a;
        cin >> x; cin >> y; cin >> a;
        paint(area, x, y, a);
        //printf("painted(%d,%d,%d)\n", x, y, a);
    }

    int wp = 0;
    for(int j = 0; j < h; j++) {
        vector<int> row = area[j];

        for(int i = 0; i < w; i++) {
            //printf("(%d,%d)=%d\n", i, j, row[i]);
            if(!row[i]) wp++;
        }
    }
    // debug
    /*
    for(int j = 0; j < h; j++) {
        vector<int> row = area[j];

        for(int i = 0; i < w; i++) {
            printf("%d ", row[i]);
        }
        printf("\n");
    }
     */

    cout << wp << endl;

    /*
    for(int i = 0; i < n; i++) {
        int x,y,a;
        cin >> x; cin >> y; cin >> a;

        vector<int> row;
        row.push_back(x); row.push_back(y); row.push_back(a);
        table.push_back(row);

        area.push_back(blank);
    }

    for(int i = 0; i < n; i++) {
        int x,y,a;
        vector<int> row = table[i];
        x=row[0]; y=row[1]; a=row[2];
    }
    */

    return 0;
}

Measured memory_bytes: 256
from collections import deque
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


ans = 0
group = 0

### BFS ###


def bfs(u):

    V[u] = group
    cnt = 1  # group に属する人数

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()
        for v in E[u]:
            if V[v] == 0:  # state を確認
                V[v] = group  # state を変更
                cnt += 1  # group に人数を追加
                q.append(v)

    return cnt


N, M = map(int, sys.stdin.readline().rstrip().split())
V = [0] * N
E = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    E[a - 1].append(b - 1)
    E[b - 1].append(a - 1)

for i in range(N):
    if V[i] == 0:
        group += 1
        ans = max(ans, bfs(i))


print(ans)


Measured memory_bytes: 45052
//#pragma GCC optimise("Ofast,unroll-loops,no-stack-protector,fast-math");
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,popcnt,avx,avx2,tune=native")
          
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
          
using namespace std;
using namespace __gnu_pbds;
          
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
          
using matrix = vector<vector<ll>>;
template<typename T>
using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
          
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
//#define int long long
 
void FAST_IO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout.setf(ios::fixed);
    //cout.precision(20);
    #ifndef _offline
    //freopen("chess.in", "r", stdin);
    //freopen("chess.out", "w", stdout);
    #endif
}

const int MAXN = 1e5 + 100;
int p[MAXN], sz[MAXN];
bool ch[MAXN];

int find_set(int u) {
    return (u == p[u] ? u : p[u] = find_set(p[u]));
}

void union_sets(int u, int v) {
    int a = find_set(u);
    int b = find_set(v);
    if (a == b) {
        return;
    }
    if (sz[a] < sz[b]) {
        swap(a, b);
    }
    p[b] = a;
    sz[a] += sz[b];
}
 
signed main() {
    FAST_IO();
    iota(p, p + MAXN, 0);
    fill(sz, sz + MAXN, 1);
    int n, q;
    ll m;
    cin >> n >> m >> q;
    vector<tuple<int, int, int>> qs(q);
    for (int i = 0; i < q; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c == 0) {
            union_sets(a, b);
        }
        qs[i] = make_tuple(a, b, c);
    }
    for (int i = 0; i < q; ++i) {
        int a, b, c;
        tie(a, b, c) = qs[i];
        if (c == 1 && find_set(a) == find_set(b)) {
            cout << "No\n";
            return 0;
        } 
        else if (c == 1) {
            ch[find_set(a)] = true;
            ch[find_set(b)] = true;
        }
    }
    set<int> setik;
    for (int i = 0; i < n; ++i) {
        setik.insert(find_set(i));
    }
    ll kek = setik.size();
    ll mn = 0, mx = 0, cnt = 0;
    for (int i : setik) {
        mn += sz[i] - 1;
        mx += sz[i] - 1;
        cnt += ch[i];
    }
    if (cnt == 0) {
        mn += kek - 1;
    }
    else if (cnt < 3) {
        if (kek < 3) {
            cout << "No\n";
            return 0;
        }
        mn += kek;
    }
    else {
        mn += kek;
    }
    mx += (kek * (kek - 1)) / 2;
    if (m >= mn && m <= mx) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
}

Measured memory_bytes: 7040
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

ll H, W, K;
vector<string> C;
vector<string> c;

void init()
{
  for (ll i = 0; i < H; i++)
  {
    C.at(i) = c.at(i);
  }
}

void drop()
{
  for (ll x = 0; x < W; x++)
  {
    string ns = "";
    for (ll y = H - 1; y >= 0; y--)
    {
      if (C.at(y).at(x) != ' ')
        ns += C.at(y).at(x);
    }

    ll cnt = 0;
    for (ll y = H - 1; y >= 0; y--)
    {
      if (cnt >= ns.size())
        C.at(y).at(x) = ' ';
      else
      {
        C.at(y).at(x) = ns.at(cnt);
        cnt++;
      }
    }
  }
}

ll erase()
{
  ll ret = 0;
  for (ll y = 0; y < H; y++)
  {
    ll tmp = 0, l = -1;
    for (ll x = 0; x < W; x++)
    {
      if (l != -1 && C.at(y).at(x) != C.at(y).at(x + 1))
      {
        if (x - l + 1 >= K)
        {
          ret += tmp * (x - l + 1);
          for (ll i = l; i <= x; i++)
          {
            C.at(y).at(i) = ' ';
          }
        }
        l = -1;
      }

      if (C.at(y).at(x) != ' ' && C.at(y).at(x) == C.at(y).at(x + 1))
      {
        if (l == -1)
        {
          l = x;
          tmp = myctoi(C.at(y).at(x));
        }
      }
    }
  }
  return ret;
}

int main()
{
  cin >> H >> W >> K;
  c = vector<string>(H);
  for (ll i = 0; i < H; i++)
  {
    cin >> c.at(i);
    c.at(i) += "#";
  }

  ll ans = 0;
  C = vector<string>(H);
  for (ll dy = 0; dy < H; dy++)
  {
    for (ll dx = 0; dx < W; dx++)
    {
      ll tmp = 0;
      init();
      C.at(dy).at(dx) = ' ';

      for (ll i = 0;; i++)
      {
        drop();
        ll sum = erase();

        /*
        cerr << dy << " " << dx << " " << i << " " << sum << endl;
        for (ll y = 0; y < H; y++)
        {
          cerr << C.at(y) << endl;
        }
        cerr << endl;
        */

        tmp += (1LL << i) * sum;
        if (sum == 0)
          break;
      }
      chmax(ans, tmp);
    }
  }

  cout << ans << endl;
}

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

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

	map<int,int> mp;
	int num=7%k;
	int ans=1;

	while(1){
		mp[num]++;
		if(num==0){
			cout << ans << endl;
			return 0;
		}
		if(mp[num]>1){
			cout << -1 << endl;
			return 0;
		}
		num=(num*10+7)%k;
		ans++;
	}

}


Measured memory_bytes: 50452
nums = input().split()
W = int( nums[0])
H = int( nums[1])
x = int( nums[2])
y = int( nums[3])
r = int( nums[4])
  
if (x - r) >= 0 and (x + r) <= W:
    if (y - r) >= 0 and (y + r) <= H:
        print( "Yes")
    else:
        print( "No")
else:
    print( "No")

Measured memory_bytes: 7712
def main():
  n=int(input())
  a=list(map(int,input().split()))
  ans,s,x=abs(sum(a)-2*a[0]),sum(a),a[0]
  for i in range(1,n-1):
    x+=a[i]
    ans=min(ans,abs(s-2*x))
  print(ans)
if __name__=='__main__':
  main()

Measured memory_bytes: 24832
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
#include <functional>

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

int main()
{
	int A,B;
	cin>>A>>B;
	if((A+B)%2)
		cout<<"IMPOSSIBLE"<<endl;
	else
		cout<<(A+B)/2<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

#define REP(i, n) for(int i = 1; i <= n; i ++)

using namespace std;

typedef pair<int, int> pii;
const int UNDEFINED = (int)1e6;
int n;

int dijkstra(int, int, vector<vector<int> >);

int main(void){
    for(int m; cin >> m >> n, n;){
        vector<vector<int> > costMap(n + 1);
        vector<vector<int> > timeMap(n + 1);

        REP(i, n){
            costMap[i].resize(n + 1);
            timeMap[i].resize(n + 1);
            REP(j, n){
                costMap[i][j] = timeMap[i][j] = UNDEFINED;
            }
        }

        while(m --){
            int a, b, cost, time;
            cin >> a >> b >> cost >> time;
            costMap[a][b] = cost;
            costMap[b][a] = cost;
            timeMap[a][b] = time;
            timeMap[b][a] = time;
        }

        int k; cin >> k;
        while(k --){
            int s, g, mode;
            cin >> s >> g >> mode;

            cout << dijkstra(s, g, ((!mode) ? costMap:timeMap)) << endl;
        }
    }

    return 0;
}

int dijkstra(int s, int g, vector<vector<int> > data){
    vector<bool> used(n + 1);
    REP(i, n) used[i] = false;

    vector<int> d(n + 1);
    REP(i, n) d[i] = (i != s) ? UNDEFINED:0;

    while(1){
        int v = UNDEFINED;
        REP(i, n) if(!used[i] && (v == UNDEFINED || d[i] < d[v])) v= i;
        if(v == UNDEFINED) break;
        used[v] = true;

        REP(i, n) d[i] = min(d[i], d[v] + data[v][i]);
    }

    return d[g];
}

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

from heapq import heappop, heappush
from collections import defaultdict

N, Q = map(int, input().split())

lst = []
l_append = lst.append
for i in range(N):
    s, t, x = map(int, input().split())
    l_append((t - x, 0, x)) #xで止まらなくなる
    l_append((s - x, 1, x)) #xで止まる

for i in range(Q):
    l_append((int(input()), 2, i))

lst.sort()
ans = [-1] * Q

#引っかかっている場所の管理
se = set()
se_hp = [] #heapで最小値を先頭に保つ

#小さい時刻から順に見ていく
# s_remove = se.remove
# s_add = se.add
for a, b, c in lst:
    if b == 0:
        se.remove(c)
    elif b == 1:
        se.add(c)
        heappush(se_hp, c)
    else:
        while se_hp and se_hp[0] not in se:
            heappop(se_hp)
        ans[c] = se_hp[0] if se_hp else -1

print ('\n'.join(map(str, ans)))

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

#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
//#define pdd pair<double,double>
#define pll pair<LL,LL>
#define pb(x) push_back(x)
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-6
#define mii map<int,int>
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
#define pi 3.14159265359
#define INF 0x7fffffff
#define next Next
#define N 200005
using namespace std;
typedef long long LL;
bitset<4000005> dp;
int main(){
	int n;
	int a[2005];
	scanf("%d",&n);
	int sum=0;
	dp[0]=1;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
		dp|=dp<<a[i];
	}
	for(int i=sum/2;i>=0;i--){
		if(dp[i]){
			printf("%d\n",sum-i);
			break;
		}
	}
}

Measured memory_bytes: 1664
from sys import stdin

def main():
    n = int(stdin.readline().rstrip())
    xs = [int(stdin.readline().rstrip()) for _ in range(n)]

    max_1 = max(xs)
    key_max = xs.index(max_1)

    for i in range(n):
        if key_max != i:
            print(max_1)
        elif i == 0:
            print(max(xs[i+1:]))
        elif i == n-1:
            print(max(xs[0:i]))
        else:
            print(max(max(xs[0:i]),max(xs[i+1:])))

if __name__ == '__main__':
    main()


Measured memory_bytes: 14068
#include<cstdio>
using namespace std;
int main()
{
	int n,m,x,sum=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&x);
		sum+=x;
	}
	if(n-sum<0)
	{
		printf("-1\n");
	}
	else
	{
		printf("%d\n",n-sum);
	}
	return 0;
} 

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


int main(){
	int _c[8]={1,2,1,2,1,4,1,4};
	vector<int> p(8),c(_c,_c+8);
	while(cin>>p[0]){
		for(int i=1;i<8;i++)cin>>p[i];
		int maxv=-1;
		vector<int> ans,t(8);
		for(int i=0;i<8;i++){
			int s=0;
			for(int j=0;j<8;j++){
				s+=min(p[j],c[(i+j)&7]);
				t[j]=c[(i+j)&7];
			}
			if(maxv<s || maxv==s && t<ans){
				ans=t;
				maxv=s;
			}
		}
		cout<<ans[0];
		for(int i=1;i<8;i++)cout<<' '<<ans[i];
		cout<<endl;
	}
	return 0;
}

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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; 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 sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int k;
    cin >> k;
    vector<bool> cnt(k, false);
    int m = 0, ans = 0;
    while (1) {
        m = m * 10 + 7;
        m %= k;
        ++ans;
        if (m==0) break;
        if (cnt[m]) {
            cout << -1 << endl;
            return 0;
        }
        cnt[m] = true;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3712
local t = {}
for i = 1, 9 do
  t[i] = io.read("*n")
end
local a, b = t[2] - t[1], t[3] - t[2]
local f = true
f = f and a == t[5] - t[4] and b == t[6] - t[5]
f = f and a == t[8] - t[7] and b == t[9] - t[8]

a, b = t[4] - t[1], t[7] - t[4]
f = f and a == t[5] - t[2] and b == t[8] - t[5]
f = f and a == t[6] - t[3] and b == t[9] - t[6]
print(f and "Yes" or "No")


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

int main() {
  int A;
  int B;
  int C;
  cin >> A >> B >> C;
  if (A <= C && C <= B){
    cout << "Yes" << endl;
}
  else if (B <= C && C <= A){
    cout << "Yes" << endl;
  }
  else{ 
    cout << "No" << endl;
  }
}

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

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

    if(S == 'a' || S == 'e' || S == 'i' || S == 'o' || S == 'u'){
        cout << "vowel" << endl;
    }
    else{
        cout << "consonant" << endl;
    }
}

Measured memory_bytes: 3604
import java.util.*;


public class Main {
	String s;
	
	class C implements Comparable<C> {
		int ind, step;

		public C(int ind, int step) {
			super();
			this.ind = ind;
			this.step = step;
		}

		@Override
		public int compareTo(C o) {
			String now = s.substring(this.ind, this.ind + this.step);
			String other = s.substring(o.ind, o.ind + o.step);
			return now.compareTo(other);
		}
		
	}
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			s = sc.next();
			int k = sc.nextInt();
			PriorityQueue<C> q = new PriorityQueue<>();
			
			HashSet<String> set = new HashSet<>();
			for(int i = 0; i < s.length(); i++){
				String now = s.substring(i, i+1);
				q.add(new C(i, 1));
			}
			int count = 1;
			while(!q.isEmpty()){
				C now = q.poll();
				String nows = s.substring(now.ind, now.ind + now.step);
				if(!set.contains(nows) && count == k){
					System.out.println(s.substring(now.ind, now.ind + now.step));
					break;
				}
				if(!set.contains(nows)){
					set.add(nows);
					count++;
				};
				if(now.ind + now.step + 1 > s.length()) continue;
				q.add(new C(now.ind, now.step+1));
			}
		}
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().doit();
	}

}


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

int n;
string s;
int id = 1;

void add_edge(int a, int b){
    cout << a << " " << b << endl;
}

int main(){
    cin >> s;
    n = s.length();
    s = " " + s;

    if(s[1] == '0' || s[n] == '1') return !printf("-1");
    for(int i = 1; i < n; i++){
        if(s[i] != s[n - i]) return !printf("-1");
    }
    add_edge(1, 2);
    int now = 2;
    id = 3;
    for(int i = 2; i <= n-1; i++){
        if(s[i] == '1'){
            add_edge(now, id);
            id++;
            now = id-1;
        }
        else {
            add_edge(now, id++);
        }
    }
}

Measured memory_bytes: 1660
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl;
#define peintD(a) cout << setprecision(10) << ans << endl;
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<int>& a,int n);

int n,m;

signed main(){
    int a,b,c,d;
    cin >> n >> a >> b >> c >> d;
    string s;
    cin >> s;
    if(c>d){
        bool ans = false;
        FOR(i,a,c-2){
            if(s[i] == s[i+1] && s[i] == '#'){
                print("No");
                return 0;
            }
        }
        FOR(i,b-1,d-1){
            if(s[i] == s[i+1] && s[i+1] == s[i+2] && s[i] == '.'){
                ans = true;
            }
        }
        if(s[b] == '.' && s[b-2] == '.') ans = true;
        if(s[b] == '.' && s[b+1] == '.') ans = true;
        (ans)? cout << "Yes" : cout << "No";
    }
    else{
        FOR(i,a,d-2){
            if(s[i] == s[i+1] && s[i] == '#'){
                print("No");
                return 0;
            }
        }
        print("Yes");
    }
    

    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<int>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

#define mem(ar,a)       memset(ar,a,sizeof ar)
#define iOS               ios_base::sync_with_stdio(false);cin.tie(NULL); 
#define pb(x)           push_back(x)
#define all(c)          c.begin(), c.end()
#define ff              first
#define ss              second
#define nl              '\n'

int main()
{
    iOS
    int n,x; cin>>n;
    stack<int> stk;
    stk.push(INT_MIN);
    long long int res=0;

    for(int i=0;i<n;i++){
        cin>>x;
        if(stk.top()<=x)
            stk.push(x);
        else
            res+=abs(x-stk.top());
    }
    cout<<res;
}



Measured memory_bytes: 4024
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
//printf("%.10f\n", N);
/*
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
    */
int main(){
    ll N,M;
    cin >> N >> M;
    string S,T;
    cin >> S >> T;//s = N,t = M
    ll num = gcd(N,M);
    ll lcm = N / num * M;
    if(num == 1){
        if(S[0] == T[0])cout << N / num * M << endl;
        else cout << -1 << endl;
    }
    else{
        bool ans = true;
        ll m = lcm / N;
        ll n = lcm / M;
        ll kai = lcm / num;
        rep(i,num){
        if(S[i * n] != T[i * m])ans = false;
        }
        if(ans)cout << lcm << endl;
        else cout << -1<< endl;
    }
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
  int a ,b ,c ,i ,n ,tmp;
  scanf( "%d" ,&n );
 
   if( n == 2 ){
     scanf( "%d %d" ,&a ,&b );
     if( a > b ){
       c = a;
       a = b;
       b = c;
     }
     printf( "1\n" );
     for( i=2 ; i<=a ; i++ ){
       if( a % i == 0 ){
	 if( b % i == 0 ){
	   printf( "%d\n" ,i );
	 }
       }
     }
   }

   else{
     scanf( "%d %d %d" ,&a ,&b ,&c );
     for( i=0 ; i<3 ; i++ ){
       if( c < b ){
	 tmp = b;
	 b = c;
	 c = tmp;
       }
       else if( b < a ){
	 tmp = a;
	 a = b;
	 b = tmp;
       }
     }
     printf( "1\n" );
     for( i=2 ; i<=a ; i++){
       if( a % i == 0 ){
	 if( b % i == 0 ){
	   if( c % i == 0 ){
	     printf( "%d\n" ,i );
	   }
	 }
       }
     }
   }

   return 0;
}

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

int main(){
  int n, r, a[100], b[100];
  while(cin >> n >> r && n && r){
    for(int i = 0;i < n;i ++){
      a[i] = n-i;
    }
    for(int i = 0;i < r;i ++){
      int c, p;
      cin >> p >> c;
      for(int j = p-1;j<p+c-1;j++){
        b[j] = a[j];
      }
      for(int j = p-2;j>=0;j--){
        a[j+c] = a[j];
      }
      for(int j = p-1;j<p+c-1;j++){
        a[j-(p-1)] = b[j];
      }
    }
    cout << a[0] << endl;
  }
  return 0;
}

Measured memory_bytes: 3044
#include <iostream>
#include <vector>
#include <map>

typedef long long ll;

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<ll> v(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    for (int i = 0; i < n; ++i) {
        v[i + 1] += v[i];
    }

    map<ll, int> mp;

    ll ans = 0;
    mp[0] = 1;
    for (int i = 0; i < n; ++i) {
        ans += mp[v[i]]++;
    }

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

Measured memory_bytes: 14336
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

#####################################


#2:10
n=int(input())
a=make_divisors(n)
ans=0
for i in range(len(a)):
    if(a[i]<n//a[i]-1):
        ans+=n//a[i]-1
print(ans)

Measured memory_bytes: 39152
import java.util.*;
  public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for(int i=0; i<=N; i++){
          int ans = 1000*i - N;
          if (ans >= 0){
            System.out.println(ans);
            break;
          } else if (ans < 0) {
            continue;
          }
        }
    }
  }

Measured memory_bytes: 36116
#include<bits/stdc++.h>
#define rep1(i,n,a) for(int i=0;i<n;i+=a)
#define rep2(i,n,a) for(int i=a;i<n;i++)
#define rep3(n)     for(int i=0;i<n;i++)
#define inarr(arr,n) rep1(i,n,1)cin>>arr[i]
#define ll long long int
#define pb push_back
#define all(v) v.begin(),v.end()
#define trav(a,x) for(auto x:a)
#define endl "\n"
#define eb emplace_back
#define fr first
#define sc second
#define gcd(a,b) __gcd(a,b)
#define pres(a,x) a.find(x)!=a.end()
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define psi pair<string,int>
#define pss pair<string,string>
#define pll pair<ll,ll>
#define vec vector<int>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ret return 0
#define pi 3.1415926536
#define hell 1000000007
#define narak 998244353
const int inf1=1e9;
const ll inf2=1e18;
using namespace std;
int dirs[4][2] ={{1,0},{-1,0},{0,1},{0,-1}};
// syntax for min priority_queue of pairs
// priority_queue<pair<ll,ll>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
ll xymodp(ll x,ll y,ll p){
    ll a=1;
    x%=p;
    while(y){
        if(y&1)a=(a*x)%p;
        x=(x*x)%p;
        y/=2;
    }
    return a;
}
void sieve(int prime[]){
   prime[0] = prime[1] = 1; 
    for (int i=2;i <=1000000;i++) { 
        if (prime[i] == 0) { 
            for (int j=i*2;j<=1000000; j+=i) { 
                if (prime[j] == 0) { 
                    prime[j] = i; 
                } 
            } 
            prime[i] = i; 
        } 
    } 
}
int prime[1000001]={0};
unordered_map<int,int> mp;
int solve(){
  int n;cin>>n;
  ll arr[n];inarr(arr,n);
  sieve(prime);
  rep3(n){
      int num=arr[i];
      unordered_map<int,int> temp;
      while (num>1){
            int factor = prime[num];   
            num /= factor; 
            temp[factor]++; 
      }
      for (auto it : temp) { 
            mp[it.first] = max(mp[it.first], it.second); 
        } 

  }
  ll ans = 1; 
  for (auto it:mp) { 
    ans = (ans *xymodp(it.fr, it.sc,hell))%hell; 
  }
  ll sum=0;
  rep3(n){
   sum=(sum+ans*xymodp(arr[i],hell-2,hell))%hell;
  } 
  cout<<sum<<endl;
  ret;
}
int main(){
    IOS;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    ret;
}
 


Measured memory_bytes: 4736
// =========
use std::cmp::{max, min};
use std::collections::{HashMap, HashSet};
use std::process::exit;

const MOD: usize = 1000000007;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    // var... 変数の識別子, $t...型を一つよむ
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        //ここで繰り返し
        input_inner!{$iter $($r)*}
    };
}

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

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

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    // 配列の最後のNestではここで型が指定されてparseされる
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// =========

fn main() {
    input! {
        n: usize,
        k: usize,
        x: [usize;n]
    }
    let mut ans = 0;
    for e in x {
        ans += min((k - e) * 2, e * 2);
    }
    println!("{:?}", ans);
}

mod tests {
    use super::*;
    #[test]
    fn check() {}
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main(){
    int i=0, j, ans=0;
    string s;
    cin >> s;
    j=s.size()-1;
    while(j>i){
        if(s[i]!=s[j]) ans++;
        i++;
        j--;
    }
    cout << ans <<endl;

    return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define ll long long
using namespace std;
const int MOD = 1000000007;
const long long INF = 1LL << 60;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> sum(n + 1, 0);
  ll ans = 0;
  for (ll i = 0; i < n; i++) {
    cin >> a[i];
    sum[i + 1] = a[i] + sum[i];
  }
  for (ll i = 2; i < n + 1; i++) {
    ll value = (sum[n] - sum[i - 1]) % MOD;
    ll num = a[i - 2] % MOD;
    ans += value * num;
    ans %= MOD;
  }
  cout << ans << endl;
}

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

int main() {
  int N,a[100001],b[100001],c[100001];
  cin>>N;
  for (int i(1);i<=N;i++) cin>>a[i]>>b[i]>>c[i];
  ll ans(0);
  ll dp[100001][3]={0};     
  dp[1][0]=a[1];
  dp[1][1]=b[1];
  dp[1][2]=c[1];
  for (int n(2);n<=N;n++){
    dp[n][0]=max(dp[n-1][1]+a[n],dp[n-1][2]+a[n]);
    dp[n][1]=max(dp[n-1][0]+b[n],dp[n-1][2]+b[n]);
    dp[n][2]=max(dp[n-1][0]+c[n],dp[n-1][1]+c[n]);
  }
  cout << max(dp[N][1],max(dp[N][0],dp[N][2]))<<endl;
  return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}

const int MAX = 510000;
const int MOD = 1000000007;

const int MAX_N = 101010;
int n,k; 
vector<int> v[MAX_N];
int flag[MAX_N];

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main() {
    cin >> n >> k;
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    COMinit();

    ll ans;

    queue<int> que;
    que.push(1);

    while(que.size()>0){
        int x = que.front();
        //cout << x << ' ';
        que.pop();
        if(x==1){
            ans = k;
            flag[1] = 1;
            int count = 0;
            rep(i,v[x].size()){
                if(flag[v[x][i]]==0){
                    count++;
                    que.push(v[x][i]);
                    flag[v[x][i]] = 1;
                }
            }
            //cout << count << endl;
            rep(i,count){
                ans *= k-1-i;
                if(k-1-i<0){
                    cout << '0' << endl;
                    return 0;
                }
                ans %= MOD;
            }
        }else{
            int count = 0;
            rep(i,v[x].size()){
                if(flag[v[x][i]]==0){
                    count++;
                    que.push(v[x][i]);
                    flag[v[x][i]] = 1;
                }
            }
            rep(i,count){
                ans *= k-2-i;
                if(k-2-i<0){
                    cout << '0' << endl;
                    return 0;
                }
                ans %= MOD;
            }
        }
        //cout << ans << ' ';
    }

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


Measured memory_bytes: 18936
#include<stdio.h>

int main(void)
{
	long k,n;
	int i;

	for(i=0;i<2;i++){
		if(i==0){
			scanf("%ld",&k);
		}
		if(i==1){
			scanf("%ld",&n);
		}
	}

	long a[n];
	long max=0,start,m;

	for(i=0;i<n;i++){
		scanf("%ld",&a[i]);
	}

	for(i=1;i<n;i++){
		m=a[i]-a[i-1];
		if(max<m){
			max=m; start=i;
		}
	}
	if((k-a[n-1])+a[0]>max){
		max=(k-a[n-1])+a[0]; start=0;
	}

	long sum=0;

	for(i=start;i<n-1;i++){
		sum+=a[i+1]-a[i];
	}
	for(i=0;i<start-1;i++){
		sum+=a[i+1]-a[i];
	}
	if(start!=0){
		sum+=(k-a[n-1])+a[0];
	}

	printf("%ld\n",sum);
	
	return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

const int MOD = 1000000007;

using namespace std;

int main(){

    int a,b;
    cin >> a >> b;
    int c = a*b;
    if(c<max(a+b,a-b)) c= max(a+b,a-b);

    cout << c << endl;

    return 0;
}

Measured memory_bytes: 256
/*
    Mbak Sana Dong
    Mbak Chaeyoung Dong
    Mbak Seulgi Dong
*/
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    int n,i,j,k,x,y,ans,curr,temp,m;
    int tc;
    string s;
    cin >> s;
    if(s.back()=='s') s += "es";
    else s += "s";
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <deque>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vector<vec> v){for(auto e:v){for(auto ee:e)cout<<ee<<" ";cout<<endl;}}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}
const int INF=1e6;
const ll int MOD=998244353;

main(){
    string s;cin>>s;
    cout<<s.substr(0,5)<<" "<<s.substr(6,7)<<" "<<s.substr(14,5);
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val S = mutableMapOf<Char, Long>()
        repeat(N) {
            val c = sc.next().toCharArray()[0]
            S[c] = (S[c] ?: 0) + 1
        }
        var ans = 0L
        val m = arrayOf(
            (S['M'] ?: 0),
            (S['A'] ?: 0),
            (S['R'] ?: 0),
            (S['C'] ?: 0),
            (S['H'] ?: 0)
        )
        for (i in 0 until 3) for (j in i + 1 until 4) for (k in j + 1 until 5) {
            ans += m[i] * m[j] * m[k]
        }
        pw.println(ans)
    }
}


Measured memory_bytes: 45540
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    //*
    int a1, b1;
    string a, b, c;
    cin >> a >> b >> a1 >> b1 >> c;
    //*/

    /*
    vector<int> vec(3);
    cin >> vec.at(0) >> vec.at(1) >> vec.at(2) ;

    sort(vec.begin(), vec.end());
    //*/
    
    //*
    if( a == c ){
        a1--;
        //cout << "Yes" << endl;
    } else {
        b1--;
        //cout << "No" << endl;
    }
    //*/
    
    cout << a1 << " " << b1 << endl;
    
    return 0; 
}


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


int main(){


    int n, i, t;

    int a = 0;

    vector<int> p;


    cin >> n;


    for( i = 0 ; i < n ; i = i + 1 ){

         cin >> t;

         p.push_back(t);

         }


    for( i = 2 ; i < n ; i = i + 1 ){

         if( p.at(i - 2) < p.at(i - 1) && p.at(i - 1) < p.at(i) ) a += 1;

         else if( p.at(i - 2) > p.at(i - 1) && p.at(i - 1) > p.at(i) ) a += 1;

         }


    cout << a << endl;

    
    return 0;


    }


Measured memory_bytes: 256