akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

	ll N, K;
	cin >> N >> K;

	if (N > K) {
		N = N % K;
	}
	ll minN = N;
	while (minN != abs(N-K)) {
		N = abs(N - K);
		if (minN > N) {
			minN = N;
		}
	}
	cout << minN << endl;
}






Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char c = sc.next().charAt(0);
		if(c=='A') System.out.println('T');
		if(c=='T') System.out.println('A');
		if(c=='C') System.out.println('G');
		if(c=='G') System.out.println('C');
	}
}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define f_in freopen("test.in","r",stdin);
#define f_out freopen("test.in","w",stdout);
#define debug(x) cerr << #x << " : " << x << "\n";
#define _ cin.sync_with_stdio(0); cin.tie(0);
#define tl cout <<"\nTime elapsed: "<<(1000 * clock() / CLOCKS_PER_SEC)<<"ms\n"
#define Func {ans += solve(i); ++i;}


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

inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

template<typename T = int>
inline T nxt(){
    char c=nc();T x=0; int f=1;
    for(;c>'9'||c<'0';c=nc())if(c=='-')f=-1;
    for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
    x*=f;
    return x;
}

const int N = 100000;
int cost[N];
pii pos[N];

int dist(int x, int y){
    return abs(pos[x].F - pos[y].F) + abs(pos[x].S - pos[y].S);
}

int main(){
#ifdef LOCAL_DEFINE
    f_in
#else
    _
#endif
    int h = nxt(), w = nxt(), d = nxt();
    rep(i,0,h) rep(j,0,w) pos[nxt()] = {i, j};
    rep(i,0,d){
        int curr = i;
        cost[curr] = 0;
        while(curr + d <= h * w) cost[curr+d] = dist(curr, curr+d) + cost[curr], curr += d;
    }
    int q = nxt();
    while(q--){
        int l = nxt(), r = nxt();
        cout << cost[r] - cost[l] << '\n';
    }
}

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

int main(){
    int n;
    cin>>n;
    vector<vector<int>> c(10,vector<int>(10));
    for(int i=1;i<=n;++i){
        int temp=i;
        while(temp/10) temp/=10;
        ++c[temp][i%10];        
    }
    long long ans=0;
    for(int i=0;i<10;++i){
        for(int j=0;j<10;++j){
            ans+=c[i][j]*c[j][i];
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3620
'''
https://youtu.be/UHfTqvaD0pk?t=22m58s
なぜ、操作がすぐ終わるのか
1stepごとに最大と最小の差が半分になるため

aa bb cc: aa最小, cc最大, 差は2(c-a)
bc ac ab: ab最小, bc最大, 差は(c-a) <- 半分!!

https://qiita.com/7shi/items/41d262ca11ea16d85abc#%E3%83%93%E3%83%83%E3%83%88%E3%81%AE%E5%90%88%E6%88%90
ビットの合成
'''

def iin(): return int(input())
def nl(): return list(map(int, input().split()))

def func(x, y, z):
    if (x | y | z) & 1:#どれかが奇数ならTrue
        return 0
    if (x == y) and (x == z):
        return -1

    #x, y, zは全て偶数なので、/ではなく//で問題ない
    x2 = (y + z) // 2
    y2 = (x + z) // 2
    z2 =  (x + y) // 2

    return func(x2, y2, z2) + 1

a, b, c = nl()
print(func(a, b, c))

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

long long n,a,m,k,q,b,c=1;
string ss,s1,s2;
int main(){
    cin>>ss;
    if (ss[0]=='S'){
        cout<<"Cloudy";
    }
    else if (ss[0]=='C'){
        cout<<"Rainy";
    }
    else{
        cout<<"Sunny";
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  long int n,temp,k,last;
  cin>>n;
  long int a[n+1],b[n+1],c[n+1];
  for(long int i=1;i<=n;i++)
  {
    cin>>a[i];
    b[i]=a[i];
    if(a[i])
      	last=i;
  }
  
  for(long int i=n/2;i>0;i--)
  {
		temp=0;
    
   for(long int j=2*i;j<=n;j=j+i)
   {
     temp+=b[j];
   }
    k=temp%2;
    if(k!=a[i])
      b[i]=1;
    else
        b[i]=0;
  }
  
  temp=0;
  for(long int i=1;i<=n;i++)
  {
    
    if(b[i])
      temp++;
  }
  
  cout<<temp<<endl;
  
  for(long int i=1;i<=n;i++)
  {
    if(b[i])
    {
      cout<<i<<" ";
    }
    
  }
  cout<<endl;
  
  return 0;
}

Measured memory_bytes: 3968
#include <stdio.h>
int main(void){
  int a,b,d,t,i=0;
  scanf("%d%d",&a,&b);
  if (b==100) d=1000;
  else if (b<10) d=10;
  else d=100;
  t=a*d+b;
  while (i*i<t) i++;
  printf("%s\n",(i*i==t)? "Yes":"No");
  return 0;
}

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

using namespace std;

void chmax(int& a, int b) { if (a < b) a = b; }

int main() {
	int N, T;
	cin >> N >> T;
	vector<pair<int, int>> AB;
	for (int i = 0; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		AB.emplace_back(a, b);
	}
	sort(AB.begin(), AB.end());

	vector<vector<int>> dp(N + 1, vector<int>(T + 1, 0));
	for (int i = 1; i <= N; ++i) {
		int a = AB[i - 1].first, b = AB[i - 1].second;
		for (int j = 0; j <= T; ++j) {
			chmax(dp[i][j], dp[i - 1][j]);
			if (j - a >= 0) { chmax(dp[i][j], dp[i - 1][j - a] + b); }
		}
	}

	int ans = 0;
	for (int i = 1; i <= N; ++i) {
		chmax(ans, dp[i][T]);
		chmax(ans, dp[i - 1][T - 1] + AB[i - 1].second);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, a, b, c, d;
  cin >> n;
	a = n / 1000;
	b = (n - a * 1000) /100;
	c = (n - a * 1000 - b * 100) /10;
	d = n - a * 1000 - b * 100 - c * 10;
  
  
  if (a == b && b == c) {
    cout << "Yes" << endl;
  }
  else if (b == c && c == d) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

}

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

using namespace std;

typedef long long ll;

#define for(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)    for(i, 0, n)
#define sz(x)        ((int)(x).size())
#define inf          1<<25

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

//typedef vector<int> vi;
//typedef vector<long long> vl;
//typedef vector<double> vd;
//typedef pair<int,int> pii;
//typedef pair<long,long> pll;
//typedef long long ll;

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

int main() {
    string a, b;
    cin >> a >> b;
    
    double x = sqrt(stoi(a + b));
    cout << (ceil(x) == floor(x) ? "Yes" : "No") << endl;
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace AtCoder2
{
    class Program
    {
        static void Main(string[] args)
        {
            checked
            {
                Console.ReadLine();
                var s = Console.ReadLine();

                var white = s.Select(c => c == '.' ? 1 : 0).ToList();

                {
                    var sum = 0;
                    for (int n = white.Count - 1; n >= 0; n--)
                    {
                        sum += white[n];
                        white[n] = sum;
                    }
                }

                var black = s.Select(c => c == '#' ? 1 : 0).ToList();

                {
                    var sum = 0;
                    for (int n = 0; n < black.Count; n++)
                    {
                        sum += black[n];
                        black[n] = sum;
                    }
                }

                white.RemoveAt(0);
                white.Add(0);
                black.RemoveAt(black.Count - 1);
                black.Insert(0, 0);

                var res = white.Zip(black, (w, b) => w + b).Min();

                Console.WriteLine(res);
            }
        }
    }
}


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

struct UnionFind {
    vector<int> par;
    vector<int> rank;

    //コンストラクタ
    UnionFind(int N) : par(N), rank(N) {
        for (int i = 0; i < N; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) swap(rx, ry);
        par[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }
};

int main() {
    int N, K, L; cin >> N >> K >> L;
    UnionFind uf1(N), uf2(N);
    for (int i = 0; i < K; i++) {
        int p, q; cin >> p >> q; p--; q--;
        uf1.unite(p, q);
    }
    for (int i = 0; i < L; i++) {
        int r, s; cin >> r >> s; r--; s--;
        uf2.unite(r, s);
    }

    map<pair<int, int>, int> MAP;
    vector<int> ans(N);

    for (int i = 0; i < N; i++) {
        pair<int, int> p = make_pair(uf1.root(i), uf2.root(i));
        MAP[p] ++;
    }
    for (int i = 0; i < N; i++) {
        pair<int, int> p = make_pair(uf1.root(i), uf2.root(i));
        cout << MAP[p] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 15872
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if(n==0) break;
			int s = 0;
			for(int i=1;i<=(int)Math.sqrt(n);i++) {
				if(n%i == 0) {
					s += i;
					if(n/i>i) s += n/i;
				}
				
			}
			s -= n;
			if(s==n) {
				System.out.println("perfect number");
			}else if(s<n) {
				System.out.println("deficient number");
			}else {
				System.out.println("abundant number");
			}
		}
	}
}


Measured memory_bytes: 26816
#include <stdio.h>

int main(int argc, char const *argv[]) {

    while (1) {
        int a, b;
        scanf("%d %d", &a, &b);

        if (a == 0 && b == 0) {
            break;
        } else {
            if (a < b) {
                printf("%d %d\n", a, b);
            } else {
                printf("%d %d\n", b, a);
            }
        }
    }

    return 0;
}


Measured memory_bytes: 1944
#include <iostream>
using namespace std;
 
int main(void)
{
    int N,K,X,Y;
    cin >> N >> K >> X >> Y;

    if(N < K){
        cout << N * X << endl;
    }
    else{
    cout << N * X - (N-K) * (X-Y) << endl;
    }
}

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

using namespace std;

int main(int argc, char* argv[])
{
  int N, M; cin >> N >> M;

  vector<pair<unsigned long, int>> shop;
  for (int i = 0; i < N; i++) {
    unsigned long A; int B;
    cin >> A >> B;
    shop.push_back(make_pair(A, B));
  }
  sort(shop.begin(), shop.end());

  int left_drink = M;
  unsigned long price = 0;
  for (vector<pair<unsigned long, int>>::iterator it = shop.begin();
       it != shop.end(); it++) {
    int buy = min(left_drink, it->second);
    price += buy*(it->first);
    left_drink -= buy;
    if (left_drink <= 0) {
      break;
    }
  }

  cout << price << endl;
  return 0;
}
  


Measured memory_bytes: 2420
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

int main(){
  int n, s;
  cin >> n >> s;
  vector<int> a(n);
  rep(snip_i, n) cin >> a.at(snip_i);
  vector<vector<mint>> dp(n+1, vector<mint>(s+1, 0));
  dp.at(0).at(0) = 1;
  rep(i,n){
    int now = a.at(i);
    rep(j, s+1){
      dp.at(i+1).at(j) += dp.at(i).at(j);
      if(now + j <= s) dp.at(i+1).at(now+j) += dp.at(i).at(j);
    }
    dp.at(i+1).at(0) += 1;
  }

  // rep(i, n+1){
  //   rep(j, s+1){
  //     cerr << dp.at(i).at(j).x << " ";
  //   }
  //   cerr << endl;
  // }

  mint ans = 0;
  rep(i, n+1){
    ans += dp.at(i).at(s);
  }
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 70784
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

#include <sstream>
#include <istream>

using namespace std;

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



int main(){
	int n;
	char s[10000];

	cin >> n;
	cin >> s;

	int r = 0;
	int b = 0;

	for(int i=0;i<n;i++){
		if(s[i]=='R') r++;
		if(s[i]=='B') 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 main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }

  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());

  int alice = 0;
  int bob = 0;

  for (int i = 0; i < N; i++) {
    if (i % 2 == 0) {
      alice += a[i];
    } else {
      bob += a[i];
    }
  }

  cout << alice - bob << endl;
};


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

int main(){
    int n,k,q;
    cin >> n >> k >> q;
    map<int, int> part;
    for(int i=0;i<n;i++){
        part[i]=0;
    }
    for(int i=0;i<q;i++){
        int a;
        cin >> a;
        if(a <= n) part[a-1]+=1;
    }
    // participant can win if answer (q-k) times
    for(auto p: part){
        int ans = p.second;
        if(ans > q-k) cout << "Yes" <<endl;
        else cout << "No" << endl;
    }
}

Measured memory_bytes: 7168
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std; 
using namespace __gnu_pbds;

#define ll long long int
#define pb push_back
#define endl "\n"
#define F first
#define S second
//typedef 1000000007 mod

#define mp map<ll,ll>
#define vc vector<ll>
#define MAX  *max_element
#define MIN  *min_element
#define lcm(a,b) (a*b)/__gcd(a,b)
#define des_sort(v) sort(v.begin(),v.end(),greater<int>())
//max xor btw range of two numbers..

#define max_XOR(a,b) (1 << int(log2(a ^ b) + 1)) - 1
#define c_ones(number) __builtin_popcountll(number)
#define flip_bits(number) static_cast<unsigned>(~number)

#define all(X) X.begin(),X.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(itr,n) for(itr=n.begin();itr!=n.end();itr++)

#define FLUSH fflush(stdout)
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb_ds tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> 
#define mod 1000000007

bool compare(pair<int,int>a , pair<int,int>b){
	return a.first==b.first ? a.second<b.second : a.first < b.first;
}

int main(){ 
	ll n,w;
	cin>>n>>w;
	vector<ll> a(n),b(n);
	rep(i,n)cin>>a[i]>>b[i];
	ll dp[n+1][w+1];
	for(int i=0;i<=n;i++){
		for(int j=0;j<=w;j++){
			if(i==0||j==0)dp[i][j]=0;
			else if(j-a[i-1]>=0){
				dp[i][j] = max(dp[i-1][j],b[i-1]+dp[i-1][j-a[i-1]]);
			}
			else dp[i][j] = dp[i-1][j];
		}
	}
	cout<<dp[n][w]<<endl;
}

Measured memory_bytes: 79104
#include<iostream>
#include<cstdlib>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iomanip>

using namespace std;
int main(){
    int a,b;
    cin >> a >> b;

    int ans(0);
    if(2 * b <= a) ans = a - 2 * b;
    else ans = 0;

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


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>

using namespace std;

#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)

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

	for(int i = 0; i < n; i++){
		double xa,ya,ra,xb,yb,rb;
		cin>>xa>>ya>>ra>>xb>>yb>>rb;
		double dist=(ya-yb)*(ya-yb)+(xa-xb)*(xa-xb);
		// AÆBªdÈçÈ¢
		if(!EQ((ra+rb)*(ra+rb),dist)&&(ra+rb)*(ra+rb)<dist)
			cout<<0<<endl;
		// ~üªðíé
		else if(((abs(ra-rb))*(abs(ra-rb))<dist&&(ra+rb)*(ra+rb)>dist))
			cout<<1<<endl;
		else if(abs(ra-rb)*abs(ra-rb)>dist){
			// Ç¿ç©ªÉ¶Ý·é
			if(ra>rb)
				cout<<2<<endl;
			else
				cout<<-2<<endl;
		}
		else
			cout<<1<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
    ll n,k;
    cin>>n>>k;
    ll s[100009];
    rep(i,100009) s[i]=0;
    rep(i,n){
        ll a=0,b=0;
        cin>>a>>b;
        s[a]+=b;
    }
    rep(i,100009){
        if(s[i]>0) k -= s[i];
        if(k<=0){
            cout<<i<<endl;
            break;
        }
    }
}


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

struct pt{
	int i,x,y;
}P[100010];

bool cmpx(const pt& a, const pt& b){return a.x < b.x;}
bool cmpy(const pt& a, const pt& b){return a.y < b.y;}

struct edge{
	int x,y,c;
	bool operator <(const edge &t)const{return c < t.c;}
}E[200020];

int U[100010];
int find(int x)
{
	if (U[x] != x) U[x] = find(U[x]);
	return U[x];
}

int main()
{
	int N;
	scanf ("%d",&N);
	for (int i=0;i<N;i++) scanf ("%d %d",&P[i].x,&P[i].y), P[i].i = i;

	int c = 0;
	sort(P,P+N,cmpx);
	for (int i=1;i<N;i++) E[c++] = {P[i-1].i,P[i].i, min(abs(P[i].x-P[i-1].x),abs(P[i].y-P[i-1].y))};
	sort(P,P+N,cmpy);
	for (int i=1;i<N;i++) E[c++] = {P[i-1].i,P[i].i, min(abs(P[i].x-P[i-1].x),abs(P[i].y-P[i-1].y))};
	sort(E,E+c);

	for (int i=0;i<N;i++) U[i] = i;
	long long ans = 0;
	for (int i=0;i<c;i++){
		int x = find(E[i].x), y = find(E[i].y);
		if (x != y){
			U[x] = y;
			ans += E[i].c;
		}
	}
	printf ("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#include <map>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
typedef long long ll;

int main(){
    ll N;
    string S;
    cin >> N >> S;
    ll ans = 0;
    REP(i,N-2){
        if(S[i] == 'A'){
            if(S[i+1] == 'B'){
                if(S[i+2] == 'C'){
                    ans += 1;
                }
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
use std::collections::HashMap;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()
}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let _n: usize = read_as_vec()[0];
    let a: Vec<i64> = read_as_vec();
    let mut hash: HashMap<i64, usize> = HashMap::new();

    let mut acc = 0;
    *hash.entry(0).or_insert(0) += 1;
    for elem in a{
        acc += elem;
        *hash.entry(acc).or_insert(0) += 1;
    }

    let mut ans = 0;
    for (_, v) in hash{
        ans += v*(v-1)/2;
    }

    println!("{}", ans);
}


Measured memory_bytes: 18060
#include <stdio.h>
#include <stdlib.h>

long long gcd(int a,int b){
    if(b==0){
        return a;
    }
    else
        return gcd(b,a%b);
}

int main()
{
    long long x,y,l=0,g=0;
    while(scanf("%lld %lld",&x,&y)==2){
        printf("%lld %lld\n",gcd(x,y),(x*y)/gcd(x,y));
    }
    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define INF 1000000000000000000
#define fn(i,n) for(int i=0;i<n;i+=1)
int w[100100],v[100100];
int dp[101][100001]={0};

signed main() {
   int n,W;cin>>n>>W;
   fn(i,n){
       cin>>w[i]>>v[i];
   }
fn(i,n+1)
{
    fn(j,W+1)
    {
        if(i==0||j==0)
        dp[i][j]=0;
        else if(w[i-1]<=j)
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
        else
        dp[i][j]=dp[i-1][j];
    }
}
cout<<dp[n][W]<<endl;
    return 0;
}



Measured memory_bytes: 80128
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)



int main(){
 int N; cin>>N;
 ULL M = 1000000007;
 ULL ans[3]={1,1,1};
 rep(i,N){
  ans[0]=ans[0]*10%M;
  ans[1]=ans[1]*9%M;
  ans[2]=ans[2]*8%M;
 }
 ans[0] += (M-ans[1])*2 + ans[2];
 ans[0] %= M;
 cout<<ans[0]<<endl;

 return 0;
}




Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

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

    vector<int> v(n, 0);
    vector<int> w(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> v[i] >> w[i];
    }
    
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= cap; j++) {
            if (j >= w[i - 1]) {
                dp[i][j] = max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    cout << dp[n][cap] << endl;

    return 0;
}



Measured memory_bytes: 6816
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    int n, m;
    cin >> n >> m;
    vvi G(n);
    vector<unordered_set<int> > G_(n);
    rep(i, n-1+m) {
        int a, b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G_[b-1].insert(a-1);
    }

    int ne;
    rep(i, n) {
        if(G_[i].empty()) ne = i;
    }


    vi ans(n, -2);
    ans[ne] = -1;
    vi depth(n, -1);
    depth[ne] = 0;
    function<void(int)> dfs = [&](int i) {
        for(int nex:G[i]) {
            if(depth[nex] < depth[i]+1) {
                ans[nex] = i;
                depth[nex] = depth[i]+1;
            }
            if(G_[nex].size() != 1) G_[nex].erase(i);
            else dfs(nex);
        }
    };

    dfs(ne);

    rep(i, n) {
        cout << ans[i]+1 << '\n';
    }
}

Measured memory_bytes: 25088
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
M = 10**9+7

# N = 10**6+10 # 必要なテーブルサイズ
N = m+n

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M


val = g1[n]*cmb(m,n,M)
val2 = 0
for i in range(1,n+1):
    val2 += cmb(n, i, M) * (g1[n-i]*cmb(m-i,n-i,M)) * pow(-1, i+1)
    val2 %= M
val2 = g1[n]*cmb(m,n,M) - val2
ans = (val*val2)%M
print(ans)

Measured memory_bytes: 127360
n = int(input())
dic = {}
for x in range(1,int(n**0.5)+1):
    for y in range(1,int(n**0.5)+1):
        for z in range(1,int(n**0.5)+1):
            ans = x**2 + y **2 + z**2 +x*y+y*z+z*x
            if ans in dic:
                dic[ans] +=1
            else:
                dic[ans] = 1

for i in range(n):
    if i+1 in dic:
        print(dic[i+1])
    else:
        print(0)

Measured memory_bytes: 11588
#include<bits/stdc++.h>
using namespace std;
int n,q,i,j,s[10000],t,c;
main(){  
  cin>>n;
  for(;i<n;cin>>s[i++]);
  cin>>q;
  for(;j<q;++j){
    cin>>t;
    for(i=0;i<n;++i)(t-s[i])||(c++,i=n);
  }
  cout<<c<<endl;
}

Measured memory_bytes: 3100
<?PHP
$line = fgets(STDIN);

$num_array = range(1,(int)$line);
$denominator = count($num_array);
$odd_array = array();
foreach($num_array as $value){
    if($value % 2 != 0){
        array_push($odd_array, $value);
    }
}

$result = count($odd_array) / count($num_array);
echo $result;

Measured memory_bytes: 4732
# https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_c
# 辞書最小にしたい
# 前から貪欲 (OK)
# 実装が分からない

from bisect import bisect_left
from string import ascii_lowercase

s = input()
k = int(input())

ac = list(ascii_lowercase) + ['a']
dmap = {}
for i in range(len(ac) - 1):
    # dmap[ac[i]] = min(i, len(ac) - i - 1)
    dmap[ac[i]] = len(ac) - i - 1
dmap['a'] = 0

ans = list(s)
output = []

for idc, c in enumerate(ans):
    if k >= dmap[c]:
        output.append('a')
        k -= dmap[c]
    else:
        output.append(c)

k %= 26
# 最後に残ったkをすすめる
new_char = chr(ord(output[-1]) + k)
output[-1] = new_char
print("".join(output))

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

struct UnionFind
{
  vector<int> sz, rank, p;

  UnionFind(int n)
  {
    sz.resize(n, 1);
    rank.resize(n, 0);
    p.resize(n);
    rep(i, n) p.at(i) = i;
  }

  int get_size(int x)
  {
    return sz.at(find(x));
  }

  int find(int x)
  {
    if (x != p.at(x))
    {
      p.at(x) = find(p.at(x));
    }
    return p.at(x);
  }

  bool same(int x, int y)
  {
    return find(x) == find(y);
  }

  void link(int x, int y)
  {
    if (rank.at(x) < rank.at(y))
      p.at(x) = y;
    else
    {
      p.at(y) = x;
      if (rank.at(x) == rank.at(y))
      {
        rank.at(x)++;
      }
    }
  }

  void unite(int x, int y)
  {
    if (!same(x, y))
    {
      int tmp = sz.at(find(x)) + sz.at(find(y));
      sz.at(find(x)) = tmp;
      sz.at(find(y)) = tmp;
    }
    link(find(x), find(y));
  }
};

int main()
{
  ll N;
  int M;
  cin >> N >> M;
  UnionFind uf(N);
  vector<pair<int, int>> edge(M);
  rep(i, M)
  {
    int A, B;
    cin >> A >> B;
    A--;
    B--;
    edge.at(i) = make_pair(A, B);
  }
  reverse(edge.begin(), edge.end());
  vector<ll> ans(M);
  ans.at(0) = N * (N - 1) / 2;
  rep(i, M - 1)
  {
    int A, B;
    tie(A, B) = edge.at(i);
    if (!uf.same(A, B))
    {
      ans.at(i + 1) = ans.at(i) - (ll)uf.get_size(A) * (ll)uf.get_size(B);
    }
    else
    {
      ans.at(i + 1) = ans.at(i);
    }
    uf.unite(A, B);
  }
  reverse(ans.begin(), ans.end());
  rep(i, M) cout << ans.at(i) << endl;
}

Measured memory_bytes: 4096
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(A: int, B: int):
    ret = 0
    if B == 1:
        ret = 0
    else:
        for i in range(100):
            if A + (A - 1) * i >= B:
                ret = i + 1
                break
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

using namespace std;

static const ll INF = 1e15;


int main() {
    int n;
    cin >> n;
    vector<vector<ll>> grid(20, vector<ll>(20, 0));
    vector<P> ss(n);
    rep(i, n) {
        double item;
        cin >> item;
        double t = item * 1e9 + 0.1;
        ll v = (ll)t;
        int a = 0;
        while(v % 2 == 0) {
            a++;
            v /= 2;
        }
        int b = 0;
        while (v % 5 == 0) {
            b++;
            v /= 5;
        }
        a = min(19, a);
        b = min(19, b);
        grid[a][b]++;
        ss[i] = make_pair(a, b);
    }

    ll sum = 0;
    rep(i, n) {
        auto f = ss[i].first;
        auto s = ss[i].second;
        grid[f][s]--;
        for (auto f2 = max(0LL, 18 - f); f2 < 20; f2++) {
            for (auto s2 = max(0LL, 18 - s); s2 < 20; s2++) {
                sum += grid[f2][s2];
            }
        }
    }

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


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

#include <vector>
#include <algorithm>
int main(){
    int n,total=0,ans=0; cin >> n;
    vector<int> d(n);
    for(int i=0; i<n; i++) {
        cin >> d.at(i);
        total += d.at(i);
    }
    for(int i=0; i<n; i++) {
        total -= d.at(i);
        ans += total*d.at(i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	int r, s, p;
	scanf("%d %d %d", &r, &s, &p);
	char t[100005];
	scanf("%s", t);
	int i;
	int ans = 0;
	int v[100005];
	for (i = 0; i < k; i++)
	{
		if (t[i] == 's')
			ans += r;
		else if (t[i] == 'p')
			ans += s;
		else
			ans += p;
		v[i] = 1;
	}
	for (i = k; i < n; i++)
	{
		if (t[i] != t[i - k])
		{
			if (t[i] == 's')
				ans += r;
			else if (t[i] == 'p')
				ans += s;
			else
				ans += p;
			v[i] = 1;
		}
		else
		{
			if (v[i - k] > 0)
				v[i] = 0;
			else
			{
				if (t[i] == 's')
					ans += r;
				else if (t[i] == 'p')
					ans += s;
				else
					ans += p;
				v[i] = 1;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

int main() {
  vector<int> v;
  v.push_back(1);
  for (int i = 1; i < 1000; i++) {
    v.push_back(v[i - 1] + i + 1);
  }
  int a, b;
  cin >> a >> b;
  for (int x = 1; x <= 499500; x++) {
    for (int i = 0; i < v.size() - 1; i++) {
      if (v[i] - x == a && v[i + 1] - x == b) {
        cout << x << endl;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
n = input()
if n[-1] == "2" or n[-1] == "4" or n[-1] == "5" or  n[-1] == "7" or n[-1] == "9":
  print("hon")
elif n[-1] == "0" or n[-1] == "1" or n[-1] == "6" or  n[-1] == "8":
  print("pon")
else:
  print("bon")

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

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

#define fill(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const int N = 5e5+10;

ll a[N];
int main(){
fast;
int n;
cin>>n;
ll totalXor = 0;
for(int i=0;i<n;i++) {
    cin>>a[i];
    totalXor = totalXor ^ a[i];
}

for(int i=0;i<n;i++) {
    cout<<(totalXor^a[i])<<" ";
}
cout<<endl;
return 0;
}

Measured memory_bytes: 5180
package main

import (
        "fmt"
        "strconv"
        "strings"
)

func min(x, y int) int {
        if x < y {
                return x
        }
        return y
}
func max(x, y int) int {
        if x > y {
                return x
        }
        return y
}

func main() {
        var N, K int
        fmt.Scanf("%d %d", &N, &K)
        a := make([]int, N, N)
        for i := 0; i < N; i++ {
                fmt.Scanf("%d", &(a[i]))
        }

        if K == 1 {
                fmt.Println("0")
                return
        }

        fmtstr := "%0" + strconv.Itoa(N-1) + "b"

        ans := 15000000000
        for i := 0; i < 1<<uint(N-1); i++ {
                s := fmt.Sprintf(fmtstr, i)

                if strings.Count(s, "1") != K-1 {
                        continue
                }

                ansT := 0
                tall := a[0]
                for j, v := range strings.Split(s, "") {
                        if v != "1" {
                        tall = max(tall, a[j+1])
                                continue
                        }
                        if a[j+1] > tall {
                                tall = a[j+1]
                        } else {
                                ansT = ansT + tall + 1 - a[j+1]
                                tall = tall + 1
                        }
                }
                ans = min(ans, ansT)
        }
        fmt.Println(ans)
}

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

using ll = long long;

int a, b, x;

void solve(){
    double ans = 0;
    if(2 * x <= a * a * b) {
        ans = atan((double)(a * b * b) / (2 * x));
    }
    else {
        ans = atan((double)(a * a * b - x) * 2 / (a * a * a));
    }
    ans = ans * 180 / M_PI;
    cout << fixed << setprecision(10) << ans;
}
int main(){
    cin >> a >> b >> x;
    solve();
    return 0;
}

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

int n,a,b,c,l[10],o[10],ans=~(1<<31);
bool len[1010],vis[10];

inline int f(int l,int s,int p)
{
	if (l==1) return abs(p-s);
	else return (l-1)*10+abs(p-s);
}

void check(int le)
{
	for (int i=1;i<le;i++)
		for (int j=i+1;j<le;j++)
		{
			int l1=i,l2=j-i,l3=le-j;
			int s1=0,s2=0,s3=0;
			for (int k=1;k<=i;k++) s1+=l[o[k]];
			for (int k=i+1;k<=j;k++) s2+=l[o[k]];
			for (int k=j+1;k<=le;k++) s3+=l[o[k]];
			ans=min(ans,f(l1,s1,a)+f(l2,s2,b)+f(l3,s3,c));
			ans=min(ans,f(l1,s1,a)+f(l2,s2,c)+f(l3,s3,b));
			ans=min(ans,f(l1,s1,b)+f(l2,s2,a)+f(l3,s3,c));
			ans=min(ans,f(l1,s1,b)+f(l2,s2,c)+f(l3,s3,a));
			ans=min(ans,f(l1,s1,c)+f(l2,s2,b)+f(l3,s3,a));
			ans=min(ans,f(l1,s1,c)+f(l2,s2,a)+f(l3,s3,b));
		}
	return ;
}

void dfs(int x,int l)
{
	if (x==l+1)
	{
		check(l);
		return ;
	}
	for (int i=1;i<=n;i++)
		if (!vis[i])
		{
			vis[i]=true;o[x]=i;dfs(x+1,l);vis[i]=false;
		}
	return ;
}

int main()
{
	scanf("%d %d %d %d",&n,&a,&b,&c);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&l[i]);
		len[l[i]]=true;
	}
	if (len[a]&&len[b]&&len[c])
	{
		puts("0");return 0;
	}
	for (int i=3;i<=n;i++) dfs(1,i);
	printf("%d\n",ans);
	return 0;
}

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

const int maxn(2e5 + 5);

int n, q, x[maxn];
ll ans = 1e18, sum[maxn], f;

struct Segment {
	ll mn[maxn << 2];
	
	void Build(int x, int l, int r) {
		mn[x] = 1e18;
		if (l == r) return;
		int mid = (l + r) >> 1;
		Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r);
	}

	void Insert(int x, int l, int r, int p, ll v) {
		mn[x] = min(v, mn[x]);
		if (l == r) return;
		int mid = (l + r) >> 1;
		p <= mid ? Insert(x << 1, l, mid, p, v) : Insert(x << 1 | 1, mid + 1, r, p, v);
	}

	ll Query(int x, int l, int r, int ql, int qr) {
		if (ql <= l && qr >= r) return mn[x];
		ll ret = 1e18;
		int mid = (l + r) >> 1;
		if (ql <= mid) ret = Query(x << 1, l, mid, ql, qr);
		if (qr > mid) ret = min(ret, Query(x << 1 | 1, mid + 1, r, ql, qr));
		return ret;
	}
} tr1, tr2;
	
inline void Solve(int cur) {
	int i;
	tr1.Build(1, 1, n), tr2.Build(1, 1, n);
	for (i = 1; i <= q; ++i) sum[i] = sum[i - 1] + abs(x[i] - x[i - 1]);
	f = abs(cur - x[1]), tr1.Insert(1, 1, n, x[0], f - x[0] - sum[1]), tr2.Insert(1, 1, n, x[0], f + x[0] - sum[1]);
	ans = min(ans, f + sum[q] - sum[1]);
	for (i = 2; i <= q; ++i) {
		f = sum[i - 1] + min(x[i] + tr1.Query(1, 1, n, 1, x[i]), tr2.Query(1, 1, n, x[i], n) - x[i]);
		tr1.Insert(1, 1, n, x[i - 1], f - x[i - 1] - sum[i]), tr2.Insert(1, 1, n, x[i - 1], f + x[i - 1] - sum[i]);
		ans = min(ans, f + sum[q] - sum[i]);
	}
}

int main() {
	int i, a, b;
	scanf("%d%d%d%d", &n, &q, &a, &b);
	for (i = 1; i <= q; ++i) scanf("%d", &x[i]);
	x[0] = a, Solve(b), x[0] = b, Solve(a), printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 15104
#include <iostream>

using namespace std;

#define rep(i,n) for(int i=0; i<(int)(n); i++)

int main() {
  int n;
  string s;
  cin >> n >> s;
  rep(i,s.size()) s[i] = 'A' + (s[i] - 'A' + n) % 26;
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n)   for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(long long i=(a);((a)<(b)?i<=(b):i>=(b));((a)<(b)?++i:--i))
#define SZ(v)      ((int)(v).size())
#define ALL(v)     (v).begin(),(v).end()
#define debug(x)   cerr<<#x<<": "<<(x)<<endl
using namespace std;
using llong = long long;
using vi    = vector<int>;
using vvi   = vector<vi >;
using vvvi  = vector<vvi >;
using pii   = pair<int,int>;
constexpr int    INF=1e9;
constexpr double EPS=1e-9;
constexpr int    MOD=1e9+7;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a){cerr<<(cnt++?' ':'>');cerr<<elem;}cerr<<endl;}

/*Binary Indexed Tree*/
template<typename Type>
struct BIT{
	int n;				//n:=(要素数).
	vector<Type> dat;	//i:=[1,n].
	
	/*constructor.*/
	BIT(int n_):n(n_),dat(n_+1,0){}
	BIT(vector<Type> &v_):n(v_.size()),dat(v_.size()+1){
		copy(ALL(v_),dat.begin()+1);
		build();
	}
	
	void build(){//木を構築する. O(N).
		for(int i=1;i<n;++i){
			if(i+(i&-i)<=n) dat[i+(i&-i)]+=dat[i];
		}
	}
	void init(Type x=0){//全要素をxで初期化する. O(N).
		fill(dat.begin()+1,dat.end(),x);
		if(x==0) return;
		build();
	}
	void add(int i,Type x){//i番目の要素にxを足す. O(log N).
		if(i<=0 or n<i) return;
		for(;i<=n;i+=(i&-i)) dat[i]+=x;
	}
	Type sum(int i){//[1,i]間の和を求める. O(log N).
		if(i<=0 or n<i) return 0;
		Type res=0;
		for(;i>0;i-=(i&-i)) res+=dat[i];
		return res;
	}
	Type range_sum(int l,int r){return sum(r)-sum(l-1);}//[l,r]間の和を求める.
};

int main(){
	int n;
	cin>>n;
	
	vector<llong> a(n);
	REP(i,n) cin>>a[i];
	
	llong ans=0LL;
	BIT<llong> tree(a);
	FOR(i,1,n){
		llong sum=tree.range_sum(i+1,n)%MOD;
		ans=(ans+a[i-1]*sum%MOD)%MOD;
	}

	cout<<ans<<endl;
}



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

const int maxN = 1e4 + 100;

int prime[maxN + 1], tot;
int n, a[maxN + 1], b[maxN + 1], g;
bool flag[maxN + 1];

vector<int> ans;

inline int read()
{
	int num = 0, f = 1;
	char ch = getchar();
	while( !isdigit( ch ) ) { if(ch == '-') f = -1; ch = getchar(); }
	while( isdigit( ch ) ) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
	return num * f;
}

inline void init()
{
	for(int i = 2; i <= n; i++)
	{
		if(!flag[i]) prime[++ tot] = i;
		for(int j = 1; j <= tot && i * prime[j] <= n; j++)
		{
			flag[ i * prime[j] ] = true;
			if(i % prime[j] == 0) break;
		}
	}
}

inline bool check(int p)
{
	if(a[0] % p) return false;
	for(int i = 0; i < p - 1; i++) b[i] = 0;
	for(int i = 0; i <= n; i++) 
		b[ i % (p - 1) ] = (b[ i % (p - 1) ] + a[i]) % p;
	for(int i = 0; i < p - 1; i++)
		if(b[i]) return false;
	return true;
}

int main()
{
	n = read();
	a[n] = read(); g = abs(a[n]);
	for(int i = n - 1; i >= 0; i--)
	{
		a[i] = read();
		if(!a[i]) continue;
		g = __gcd(g, abs(a[i]));
	}

	for(int i = 2; i * i <= g; i++)
		if(g % i == 0)
		{
			ans.push_back(i);
			while(g % i == 0) g /= i;
		}
	if(g > 1) ans.push_back(g);

	init();

	for(int i = 1; i <= tot; i++)
		if(check(prime[i])) ans.push_back(prime[i]);

	sort(ans.begin(), ans.end());
	ans.erase( unique(ans.begin(), ans.end()), ans.end() );

	for(int i = 0; i < ans.size(); i++) printf("%d\n", ans[i]);
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 998244353;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(22);
  double r1, r2;
  cin >> r1 >> r2;
  cout << 1. / (1. / r1 + 1. / r2) << endl;
}


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

int main() {
	long long n, k;
	cin >> n >> k;
	if (k >= n) {
		cout << min(n, k - n) << '\n';
	}
	else {
		cout << min(n % k, k - (n % k)) << '\n';
	}
}

Measured memory_bytes: 256
import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}
import java.lang

import scala.reflect.ClassTag

object Main {
  def get[T: ClassTag](implicit in: BufferedReader, converter: String => T): T = {
    converter(in.readLine)
  }

  def getArray[T: ClassTag](implicit in: BufferedReader, converter: String => T): Array[T] = {
    get[String].split("\\s+").map[T](converter)
  }

  implicit val idConverter: String => String = s => s
  implicit val intConverter: String => Int = s => Integer.parseInt(s)
  implicit val longConverter: String => Long = s => lang.Long.parseLong(s)

  def get[T1, T2](
                   implicit in: BufferedReader,
                   converter1: String => T1,
                   converter2: String => T2
                 ): (T1, T2) = {
    getArray[String] match {
      case Array(v1, v2) => (converter1(v1), converter2(v2))
    }
  }

  def get[T1, T2, T3](
                       implicit in: BufferedReader,
                       converter1: String => T1,
                       converter2: String => T2,
                       converter3: String => T3
                     ): (T1, T2, T3) = {
    getArray[String] match {
      case Array(v1, v2, v3) => (converter1(v1), converter2(v2), converter3(v3))
    }
  }

  implicit class TimesInt(val n: Int) {
    def times(f: Int => Unit): Unit = {
      for (i <- 0 until n) {
        f(i)
      }
    }
  }

  def main(args: Array[String]): Unit = {
    implicit val in: BufferedReader = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))

    out.println(getArray[Int].product)

    out.flush()
  }
}

Measured memory_bytes: 54852
n = int(input())
a = list(map(int,input().split()))
k = 1000000007

aa = [0]*(n+1)
aa[0] = 3
ans = 1
for i in range(n):
    ans = ans * aa[a[i]] % k
    aa[a[i]] -= 1
    aa[a[i]+1] += 1
print(ans)
    
    
    

Measured memory_bytes: 13964
# https://abc100.contest.atcoder.jp/tasks/abc100_c
# C - *3 or /2

# C_star_by_3_or_div_by_2.py

N = int(input())
A = list(map(int, input().strip().split(" ")))

num_division = (-1) * N

for a in A:
    while int(a) == a:
        a = a/2
        num_division += 1

print(num_division)


Measured memory_bytes: 4148
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <cstdlib>
#include <utility>
#include <map>
#include <set>
#include <ios>
#include <iomanip>
#include <functional>
#include <queue>

#define int long long
int inf = (1LL <<  62);
using namespace std;

signed main(){
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < s.size() - 1; i++){
        if(s[i] != s[i + 1]){
            ans++;
        }
    }
    cout << ans;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[200005];
int main()
{
    int  d,t,s;
    cin >> d >> t>> s;
    int dis = s*t;
    if(dis>=d)
        cout << "Yes\n";
    else
        cout << "No\n";
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, x;
  cin >> a >> b >> x;
  // a: cat, b:dog or cat

  if ((x <= a + b - 1) && (x >= a)) {
    cout << "YES" << endl;
  }else {
    cout << "NO" << endl;
  }
}

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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


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

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

int main() {
  int h, w;
  cin >> h >> w;
  for(int i = 0; i < h; i++) {
    for(int j = 0; j < w; j++) {
      string t;
      cin >> t;
      if(t == "snuke") {
        cout << (char) (j + 'A') << i + 1 << endl;
      }
    }
  }
}

Measured memory_bytes: 256