akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define MAX 10005
#define INFTY INT_MAX
int n;

struct NW {
    int point, weight;
};

vector<vector<NW> > ve;
vector<NW> vNW;
NW nw;

void dijkstra() {
    int color[MAX], d[MAX];
    for (int i = 0; i < n; i++) {
        color[i] = 0;
        d[i] = INFTY;
    }
    d[0] = 0;
    while (1) {
        int u, minv = INFTY;
        for (int i = 0; i < n; i++) {
            if (color[i] != 1 && d[i] < minv) {
                u = i;
                minv = d[i];
            }
        }
        if (minv == INFTY) 
            break;
        color[u] = 1;
        for (int i = 0; i < ve[u].size(); i++) {
            int v = ve[u][i].point;
            int c = ve[u][i].weight;
            if (color[v] != 1 && d[u] + c < d[v]) {
                d[v] = d[u] + c;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << i << " " << d[i] << endl;
    }
}

int main(void) {
    cin >> n;
    ve.resize(n);
    int u, k;
    for (int i = 0; i < n; i++) {
        vNW.clear();
        cin >> u >> k;
        while (k--) {
            cin >> nw.point >> nw.weight;
            vNW.push_back(nw);
        }
        ve[u] = vNW;
    }

    dijkstra();
}


Measured memory_bytes: 6676
#include<stdio.h>
int main()
{
	//freopen("C:\\Users\\J2401\\Desktop\\In.txt","r",stdin);
	//freopen("C:\\Users\\J2401\\Desktop\\out.txt","w",stdout);

	int a[3][6] = {0};
	int time[3][3] = {0};
	int x,y;
	
	for(x=0; x<3; x++)
	{	
		for(y=0; y<6; y++)
		{
			scanf("%d",&a[x][y]);
		}
	}

	for(x=0; x<3; x++)
	{
		if((time[x][2] = a[x][5] - a[x][2]) < 0)
		{
			if(a[x][4] != 0)
			{
				a[x][4]--;
			}
			else
			{
				a[x][3]--;
				a[x][4] = 59;
			}
			time[x][2] = 60 + a[x][5] - a[x][2];
		}
		if((time[x][1] = a[x][4] - a[x][1]) < 0)
		{
			if(a[x][3] != 0)
			{
				a[x][3]--;
				
			}
			time[x][1] = 60 + a[x][4] - a[x][1];
		}
		time[x][0] = a[x][3] - a[x][0];
	}

	for(x=0; x<3; x++)
	{
		for(y=0; y<3; y++)
		{
			printf("%d",time[x][y]);
			if(y != 2)
				printf(" ");
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 604
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n;
    cin>>n;
    long long int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    long long int dp[n][n],graph[n][n];
    for(int i=0;i<n;i++)
    {
        dp[i][i]=a[i];
        graph[i][i]=0;
    }
    
    for(int i=1;i<n;i++)
    {
        for(int j=i-1;j>=0;j--)
        {
            if(i!=j)
               {
                   dp[j][i]=max(a[i]+graph[j][i-1],a[j]+graph[j+1][i]);
                   graph[j][i]=min(dp[j][i-1],dp[j+1][i]);
               }
        }
    }
    
    cout<<dp[0][n-1]-graph[0][n-1]<<"\n";
    
    return 0;
}

Measured memory_bytes: 140160
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int main(int argc, const char *argv[]) {
  int N;
  double sum = 0.0;
  cin >> N;
  vector<int> A(N);

  for(int i=0;i<N;i++){
    cin >> A[i];
  }
  for(int i=0;i<N;i++){
    sum += 1.0 / (double)A[i];
  }
  printf("%f\n", 1.0 / (double)sum);

  return 0;
}


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

using i64 = int64_t;

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

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

template <i64 p>
class fp {
    public:
    i64 x;
    fp() : x(0) {}
    fp(i64 x_) : x((x_ % p + p) % p) {}
    fp operator+() const { return fp(x); }
    fp operator-() const { return fp(-x); }
    fp& operator+=(const fp& y) {
        x += y.x;
        if (x >= p) x -= p;
        return *this;
    }
    fp& operator-=(const fp& y) { return *this += -y; }
    fp& operator*=(const fp& y) {
        x = x * y.x % p;
        return *this;
    }
    fp& operator/=(const fp& y) { return *this *= fp(inverse(y.x)); }
    fp operator+(const fp& y) const { return fp(x) += y; }
    fp operator-(const fp& y) const { return fp(x) -= y; }
    fp operator*(const fp& y) const { return fp(x) *= y; }
    fp operator/(const fp& y) const { return fp(x) /= y; }
    bool operator==(const fp& y) const { return x == y.x; }
    bool operator!=(const fp& y) const { return !(*this == y); }
    i64 extgcd(i64 a, i64 b, i64& x, i64& y) {
        i64 d = a;
        if (b != 0) {
            d = extgcd(b, a % b, y, x);
            y -= (a / b) * x;
        } else {
            x = 1;
            y = 0;
        }
        return d;
    }
    i64 inverse(i64 a) {
        i64 x, y;
        extgcd(a, p, x, y);
        return (x % p + p) % p;
    }
};

template <i64 p>
i64 abs(const fp<p>& x) { return x.x; }

template <i64 p>
istream& operator>>(istream& is, fp<p>& x) {
    is >> x.x;
    return is;
}

template <i64 p>
ostream& operator<<(ostream& os, const fp<p>& x) {
    os << x.x;
    return os;
}

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

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

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

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

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

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

// double(64bit浮動小数)のn分探索のループ回数の上限(2分探索なら50でも十分かもしれない). long double(80ビットの x87 浮動小数点型?)だと, 2分探索であってもこれだと足りないケースがある気がするので, もうちょっと余裕を持たせた方が良さそう.
constexpr i64 max_loop = 100;

void solve() {
    //constexpr i64 mod = 1'000'000'007;
    long double R;
    cin >> R;

    cout << 2*acos(-1)*R << endl;
}

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


Measured memory_bytes: 3792
import sys

N = int(raw_input())
votes = []
for _ in range(N):
	t, a = map(int, raw_input().split())
	votes.append((t, a))

pt, pa = 0, 0

for v in votes:
	if (v[0] >= pt and v[1] >= pa):
		pt, pa = v[0], v[1]
	else:
		if (pt % v[0]):
			nt = pt / v[0] + 1
		else:
			nt = pt / v[0]
		if (pa % v[1]):
			na = pa / v[1] + 1
		else:
			na = pa / v[1]
		m = max(nt, na)
		pt, pa = v[0] * m, v[1] * m

print str(pt + pa)


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

signed main(){
    int m,n;
    static int fare[111][111], time[111][111];
    while(cin >> m >> n && m){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                fare[i][j] = time[i][j] = (i == j) ? 0 : 1e8;
            }
        }
        for(int i = 0; i < m; i++){
            int u, v, a, b;
            cin >> u >> v >> a >> b;
            fare[u][v] = fare[v][u] = a;
            time[u][v] = time[v][u] = b;
        }
        for(int k = 1; k <= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    fare[i][j] = min(fare[i][j], fare[i][k] + fare[k][j]);
                    time[i][j] = min(time[i][j], time[i][k] + time[k][j]);
                }
            }
        }
        int t;
        cin >> t;
        for(int i = 0; i < t; i++){
            int u, v, q;
            cin >> u >> v >> q;
            if(q == 0) cout << fare[u][v];
            else cout << time[u][v];
            cout << endl;
        }
    }
}

Measured memory_bytes: 1252
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,K;
  cin>>N>>K;
  int arr[N];
  for(int i=0;i<N;i++){
  cin>>arr[i];
  }
  int dp[N]={0};
  dp[N-2]=abs(arr[N-2]-arr[N-1]);
  for(int i=N-2;i>=0;i--){
  int j=i+1;
    int minval=INT_MAX;
    while(j<N&&j<=i+K){
    minval=min(minval,abs(arr[i]-arr[j])+dp[j]);
      j++;
    }
    dp[i]=minval;
  }
  cout<<dp[0];
  return 0;
}

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

using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;

template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template <class T, class U>
void chmax(T &a, U b) {
    if (a < b) a = b;
}
template <class T, class U>
void chmin(T &a, U b) {
    if (b < a) a = b;
}

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 50);

void solve(long long N, long long A, long long B) {

    int x = N / (A + B);
    int y = N % (A + B);

    cout << x * A + min(y, A) << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    long long N;
    scanf("%lld", &N);
    long long A;
    scanf("%lld", &A);
    long long B;
    scanf("%lld", &B);
    solve(N, A, B);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;

int N, M;
VI G[200010];
int ans[200010];

void dfs(int now, int pa) {
	//cout << now << endl;
	fore(to, G[now])if (to != pa) {
		//cout << ans[to] << endl;
		if (ans[to] == 0) {
			ans[to] = now + 1;
			dfs(to, now);
		}
	}
	//cout << now << endl;
}


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

	cin >> N >> M;
	REP(i, M) {
		int a, b; cin >> a >> b;
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	//dfs(0, -1);

	queue<int>Q;
	Q.push(0);
	
	
	while (!Q.empty()) {
		int now = Q.front();
		Q.pop();
		fore(to, G[now]) {
			//cout << to  << " " << now << endl;
			if (ans[to] == 0) {
				ans[to] = now + 1;
				Q.push(to);
			}
		}
	}

	cout << "Yes" << endl;
	FOR(i, 1, N) {
		cout << ans[i] << endl;
	}


	return 0;
}



Measured memory_bytes: 15348
//Author : Siriuslight
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#define FIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0),cout<<setprecision(10)<<fixed;
#define int long long
#define F first
#define S second

using namespace std;
using namespace __gnu_pbds;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

typedef long long ll;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const ll inf = 1e9+100, N = 2e5+5;
const ll INF = 1e18+100, MOD = 1e9+7;

ll powmod(ll a,ll b,ll m=MOD){ll r=1;while(b>0){if(b&1)r=r*a%m;a=a*a%m;b>>=1;}return r;}
ll power(ll a,ll b){ll r=1;while(b>0){if(b&1)r=r*a;a=a*a;b>>=1;}return r;}
ll gcd(ll a,ll b){if(!b)return a;return gcd(b,a%b);}
ll inv(ll a, ll m = MOD){return powmod(a,m-2,m);}
ll lcm(ll a,ll b){return(a*b)/gcd(a,b);}

//ordered_set X;
//X.insert(3);
//X.order_of_key(3) no of elements less than 3
//*X.find_by_order(n) nth greatest element(0-indexed)

int n, a[N], dp[N];

int solve(int id){
    if(id >= n)
        return 0;
    int &res = dp[id];
    if(res != -1) return res;
    res = inf;
    if(id + 1 <= n)
        res = min(res, abs(a[id] - a[id + 1]) + solve(id + 1));
    if(id + 2 <= n)
        res = min(res, abs(a[id] - a[id + 2]) + solve(id + 2));
    return res;
}
int32_t main(){
    FIO;
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    memset(dp, -1, sizeof(dp));
    cout << solve(1);
}


Measured memory_bytes: 5760
import sys
input = sys.stdin.readline
enum = enumerate

import collections
import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def dist(x1,y1,x2,y2):
	return abs(x1-x2)+abs(y1-y2)

def main():
	S = input().rstrip()
	#vS = [input().rstrip() for _ in [0,]*N]
	N = len(S)
	oA = ord("a")
	vD = [chr(i+oA) for i in range(26)]
	#vD += [".","#"]

	res = 0
	M = N
	
	# dp[i..M][d..26] = y/n
	vN = [[0,]*26 for _ in "*"*M]

	for i,s in enum(S):
		d = ord(s)-oA
		vN[i][d] = 1

	while M:
		ok = 0
		for d in range(26):
			for i in range(M):
				if not vN[i][d]: break
			else:
				ok = 1; break
		if ok: break
		M -= 1
		for d in range(26):
			for i in range(M):
				vN[i][d] |= vN[i+1][d]
	
	res = N - M
	print(res)
	#sT = "No Yes".split()
	#print(sT[res])
	

if __name__ == "__main__":
	main()


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

using namespace std;
typedef long long ll;

int main() {
	int n;
	cin >> n;
	
	int max = 0;
	int total = 0;
	for(int i=0; i < n; i++) {
		int val;
		cin >> val;
		if(val > max) {
			total += max;
			max = val;
		}
		else {
			total += val;
		}
	}
	
	cout << (total > max ? "Yes" : "No"); 
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <map>

using namespace std;

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

void solve()
{
	int N;
	cin >> N;
	unsigned long long int x, y;
	cin >> x >> y;
	for (int i = 1; i < N; ++i)
	{
		unsigned long long int T, A;
		cin >> T >> A;
		unsigned long long int coef = max(x / T, y / A);
		while (!(x <= T * coef && y <= A * coef))
		{
			coef += 1;
		}
		x = T * coef;
		y = A * coef;
	}
	cout << x + y << endl;
}

int main()
{
	solve();
	return(0);
}

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  VLL a(n);
  rep(i,n){
    cin >> a[i];
  }
  map<ll,int> mp;
  rep(i,n) mp[a[i]]++;

  if(mp.find(0) != mp.end() ){ // 0がある場合
    if(mp.size() >= 3){ // over 3
      cout << "No" << "\n";
      return 0;
    }else if(mp[0] == n){ // 0 しかない
      cout << "Yes" << "\n";
      return 0;
    }else{ // 2
      if(n % 3 == 0 && mp[0] == n/3) cout << "Yes" << "\n";
      else cout << "No" << "\n";
      return 0;
    }
  }else if(mp.size() == 3){// 3種類で構成
    ll sum = 0;
    for(auto x: mp) sum ^= x.first;
    if(sum != 0){
      cout << "No" << "\n";
      return 0;
    }
    set<int> st;
    for(auto x: mp) st.insert(x.second);
    if(st.size() == 1){
      cout << "Yes" << "\n";
      return 0;
    } else {
      cout << "No" << "\n";
      return 0;
    }
  }
  else{
    cout << "No" << "\n";
    return 0;
  }

  return 0;
}


Measured memory_bytes: 5760
let a = readLine()!

var arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j",
"k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
"u", "v", "w", "x", "y", "z"]
che(chra: a)

func che(chra: String) -> Void {
    for i in arr {
        if chra == i {
            print("a")
            return
        }
    }
    print("A")
}


Measured memory_bytes: 7656
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

struct P {
    bool operator<(const P &p) const {
        return s != p.s ? s < p.s : i < p.i;
    }
    int s, i;
};

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

    int n, k;
    cin >> n >> k;

    vector<P> p(n + 1);
    p[0] = { 0, 0 };

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        a--;

        p[i + 1] = { (p[i].s + a) % k, i + 1 };
    }
    sort(p.begin(), p.end());

    ll r = 0;
    for (int i0 = 0, i1 = 0; i1 <= n; i1++) {
        while (p[i0].s != p[i1].s || p[i0].i + k <= p[i1].i) i0++;
        r += i1 - i0;
    }

    cout << r << endl;

    return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
double Pi = 3.1415926535897932384626;
 
//vector<ll> G[550010];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
ll mod = 1000000007;
/*
2000000011 is prime
2000000033 is prime
*/

ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}


//ll fact[800005],rfact[800005];
/*
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=800000; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[800000] = rui(fact[800000],mod - 2);
    for(ll i=800000; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod) * rfact[n-r]) % mod;}
*/
 
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r;
ll k,ans;
ll x[500005],y[500005],z[500005];
char s[500005];



int main(){
    cin >> n >> k;
    for(i=0;i<n;i++){
        cin >> x[i];
        y[x[i]]++;
    }
    for(i=1;i<=2000;i++){
        y[i] += y[i-1];
    }
    for(i=0;i<n;i++){
        num = y[2000] - y[x[i]];
        a = k * (k - 1) / 2;
        a %= mod;
        a *= num;
        a %= mod;
        ans += a;
        ans %= mod;
        //num = y[x[i] - 1];
        //ans += (num * (k * (k - 1) / 2) % mod) % mod;
        ans %= mod;
        //p(ans);
    }
    for(i=0;i<n;i++){
        for(j=0;j<i;j++){
            if(x[j] > x[i]){
                ans += k;
                ans %= mod;
            }
        }
    }

    p(ans);
    
    return 0;
}






Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include<random>
#include<math.h>
#include<limits.h>
#include<iterator>
#include<queue>
#include<functional>
#define rep(i,a) for(int i=0;i<a;i++)
#define nrep(i,a,b) for(int i=a;i<b;i++)
#define mrep(i,a) for(int i=a;i>=0;i--)
#define ll long long
#define vl vector<ll> 
#define vvl vector<vector<ll> > 
#define vb vector<bool> 
#define vvb vector<vector<bool> > 
#define INF 11234567890123456789
using namespace std;

int main(){
	ll n; cin >> n;
	ll ans = 0;
	rep(i, n){
		ll l, r; cin >> l >> r;
		ans += r - l + 1;
	}cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] a=new int[101];
		int max=0,min=1000;
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
			if(a[i]<min)		min=a[i];
			if(a[i]>max)		max=a[i];
		}
		System.out.println(max-min);
	}

}

Measured memory_bytes: 20948
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<unistd.h>
#include <array>
#include <map> 




using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd(int a, int b)
{
	return a == 0 ? b : gcd(b % a, a);
}
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a';
    if((ans < 0) || (ans > 25)){
        ans = 26;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}

int binary_searchh(long long x,long long k[],int n){
  int l=0;
  int r=n;
  while(r-l>=1){
    int i=(l+r)/2;
    if(k[i]==x)return i;
    else if(k[i]<x)l=i+1;
    else r=i;
  }
  return -1;
}

struct File {
    int aa;
    int bb;

    File(const int& aa, const int& bb)
        : aa(aa), bb(bb) {}
};

bool operator<(const File& a, const File& b)
{
    // ファイル種別、ファイル名の順番で優先順位を付けて比較
    return std::tie(a.aa, a.bb) < std::tie(b.aa, b.bb);
}

long long kaijo(long long x){
  long long l=10*10*10*10*10*10*10*10*10+7;
  long long sum=1;
  for(int i=x;i>0;i--){
    sum*=i;
    if(sum>l){
      sum%=l;
    }
  }
  return sum;
}






int main(){
  int N;
  cin>>N;
  long long xx=1000000007;
  long long sum=1;
  int l[N+1];
  for(int i=0;i<N+1;i++){
    l[i]=i;
  }
  int m[N+1];
  for(int i=0;i<N+1;i++){
    m[i]=1;
  }
  for(int i=2;i<N+1;i++){
    for(int j=2;j<=i;j++){
      while(l[i]%j==0){
        l[i]/=j;
        m[j]++;
      }
    }
  }
  for(int i=0;i<N+1;i++){
    sum*=m[i];
    if(sum>xx){
      sum%=xx;
    }
  }
  cout<<sum<<endl;


}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int A,B;
    cin>>A>>B;
    int count=0;
    for(int i=A;i<=B;i++){
        if(i/1000==i%10*10+i/10%10){count++;}
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<assert.h>

using namespace std;
using ll = long long;
#define REP(i,N) for(int i=0;i<N;i++)

ll N,M,P;
vector < vector<ll> > edges;
vector < vector<ll> > adj,adj_rev;
vector<bool> used,used_rev;

vector<ll> dist;

void dfs(ll node){
    if (adj[node].size()==0){
        return;
    }
    else{
        for(auto next :adj[node]){
            if(used[next]){
                continue;
            }
            used[next]=true;
            dfs(next);
        }
    }
}
void dfs2(ll node){
    if (adj_rev[node].size()==0){
        return;
    }
    else{
        for(auto next :adj_rev[node]){
            if(used_rev[next]){
                continue;
            }
            used_rev[next]=true;
            dfs2(next);
        }
    }
}

int main(){
    cin >>N >>M>>P;

    dist.resize(N);
    adj.resize(N);
    adj_rev.resize(N);
    used.resize(N,false);
    used_rev.resize(N,false);
    REP(i,N)dist[i]=-1e10;

    REP(i,M){
        ll a,b,c;
        cin >> a >> b>>c;
        vector<ll> e{a-1,b-1,c-P};
        edges.push_back(e);
        adj[a-1].push_back(b-1);
        adj_rev[b-1].push_back(a-1);
    }

    used[0]=true;
    used_rev[N-1]=true;
    dfs(0);
    dfs2(N-1);

    //REP(i,N){cout<<used[i]<<" ";}cout<<endl;
    //REP(i,N){cout<<used_rev[i]<<" ";}cout<<endl;

    dist[0]=0;
    REP(i,N+1){
        bool update=false;
        REP(j,M){
            ll from=edges[j][0];
            ll to=edges[j][1];
            ll cost=edges[j][2];
            
            if(used[to]&&used[from]&&used_rev[to]&&used_rev[from]){
                if(dist[to]<dist[from]+cost){
                    dist[to]=dist[from]+cost;
                    update=true;
                }
            }
        }
        if(!update){
            break;
        }
        if(i==N){
            cout<<-1<<endl;
            return 0;
        }
    }

    //REP(i,N){cout<<dist[i]<<" ";}cout<<endl;

    
    if(dist[N-1]<0){
        cout<<0<<endl;
    }
    else{
        cout<<dist[N-1]<<endl;
    }
    return 0;
}


Measured memory_bytes: 4228
#include <stdio.h>

int main(void) {
    int W, H;
    for (;;) {
        scanf("%d %d", &W, &H);
        if (W == 0 && H == 0) {
            return 0;
        } else {
            for (int i = 1; i <= W; i++) {
                if (i % 2 != 0) {
                    for (int j = 1; j <= H; j++) {
                        if (j % 2 != 0) {
                            printf("#");
                        } else {
                            printf(".");
                        }
                    }
                } else {
                    for (int j = 1; j <= H; j++) {
                        if (j % 2 != 0) {
                            printf(".");
                        } else {
                            printf("#");
                        }
                    }
                }
                puts("");
            }
        puts("");
        }
    }
}


Measured memory_bytes: 2136
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */
string solveA(){
    ll R; cin >> R;
    return R < 1200 ? "ABC": R < 2800?"ARC":"AGC";
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << solveA() << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<(int)(n); i++)
#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)
using namespace std;

int main(){
  int r,g,b; cin >>r >>g >>b;
  int check=r*100+g*10+b;
  cout <<(!(check%4) ? "YES":"NO") <<endl;
  return 0;
}


Measured memory_bytes: 256
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
  let mut s = String::new();
  std::io::stdin().read_line(&mut s).ok();
  s.trim().split_whitespace()
    .map(|e| e.parse().ok().unwrap()).collect()
}
 
fn main() {
  let ap: Vec<u32> = read_vec();
  let ans = (ap[0] * 3 + ap[1]) / 2;

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


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

#define int long long
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; }

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

	vector<pair<int, int>> fi, la;
	
	for(int i = 0;i < n;i++){
		string s;
		cin >> s;
		int ll, rr;
		ll = 0;
		int st = 0;
		for(int i = 0;i < s.size();i++){
			if(s[i] == '('){
				st++;
			}else{
				st--;
				if(st < 0){
					st = 0;
					ll++;
				}
			}
		}
		rr = st;
		if(ll < rr){
			fi.push_back({ll, rr});
		}else{
			la.push_back({rr, ll});
		}
	}

	int r = 0;
	sort(fi.begin(), fi.end());
	for(int i = 0;i < fi.size();i++){
		if(r < fi[i].first){
			cout << "No" << endl;
			return 0;
		}
		r += fi[i].second-fi[i].first;
	}


	sort(la.begin(), la.end());
	int l = 0;
	for(int i = 0;i < la.size();i++){
		if(l < la[i].first){
			cout << "No" << endl;
			return 0;
		}
		l += la[i].second-la[i].first;
	}

	cout << (r == l ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 18892
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr ll MODN = 1000000007;
ll n, dp[1000001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n, dp[0] = 1, dp[1] = dp[0] + n;
	for (int i = 2; i <= n; ++i) {
		dp[i] = (n - 1) * (n - 1);
		int l = i - (n + 1), r = i - 3;
		if (r >= 0) dp[i] += dp[r], r = -1;
		dp[i] += r - l + 1;
		dp[i] += 2 * dp[i - 1] - dp[i - 2];
		dp[i] %= MODN;
	}
	cout << (dp[n] - dp[n - 1] + MODN) % MODN << endl;
	return 0;
}

Measured memory_bytes: 8064
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i<x;i++)
int dp[105];
int m[105]={};
int u[105][2]={};
int v[105][2]={};
int a[105]={};
int gcd(int a,int b)
{
	if(a%b==0) return b;
	return gcd(b,a%b);
}
int main()
{
	
	while(1)
	{
		int n;
		scanf("%d",&n);
		if(!n) return 0;
		queue<int>que;
		for(int i=1;i<=n;i++)
		{
			int aa,b,c,d;
			scanf("%d %d %d %d",&aa,&b,&c,&d);
			u[i][0]=c;
			u[i][1]=d;
			if(c)a[i]++;
			if(d)a[i]++;
			int di=gcd(aa,b);
			v[i][0]=aa/di;
			v[i][1]=b/di;
			if(!a[i]) que.push(i);
		}
		fill(dp,dp+105,1);
		int ret;
		while(!que.empty())
		{
			int r=que.front(); que.pop();
			int bas=1;
			for(int i=0;i<2;i++)
			{
				if(u[r][i])
				{
					int f=dp[u[r][i]]/gcd(dp[u[r][i]],v[r][1-i]);
					bas=bas/gcd(bas,f)*f;
				}
			}
			dp[r]=bas*(v[r][0]+v[r][1]); ret=dp[r];
			for(int i=1;i<=n;i++)
			{
				if(u[i][0]==r || u[i][1]==r)
				{
					a[i]--;
					if(!a[i]) que.push(i);
				}
			}
		}
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 1192
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
K = int(input())
count = 0

if B - A > K:
    count += 1
elif C - A > K:
    count += 1
elif D - A > K:
    count += 1
elif E - A > K:
    count += 1
elif C - B > K:
    count += 1
elif D - B > K:
    count += 1
elif E - B > K:
    count += 1
elif D - C > K:
    count += 1
elif E - C > K:
    count += 1
elif E - D > K:
    count += 1

if count >= 1:
    print(':(')
else:
    print('Yay!')



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using V = vector<int>;
using P = pair<int, int>;
#define rep(i, n) for(int i=0; i<int(n); ++i)


// 有向グラフの接続行列 B に対し，線形方程式 Bx = c を (必要なら mod 2 で) 解くライブラリ
template<typename T>
struct LinearSystemIncidence {
  struct Edge {
    int id, to; bool fwd;
    Edge(int i, int t, bool f) : id(i), to(t), fwd(f) {}
  };

  int n, m;
  bool mod2;
  vector<T> x;
  vector<bool> seen;
  vector<vector<Edge>> G;
  
  LinearSystemIncidence(int n, vector<P> &E, bool mod2=false) : n(n), m(E.size()), G(n), mod2(mod2) {
    rep(i, m) {
      G[E[i].first].emplace_back(i, E[i].second, true);
      G[E[i].second].emplace_back(i, E[i].first, false);
    }
  }

  T dfs(vector<T> &c, int u) {
    seen[u] = true;
    T res = c[u];
    for (Edge e : G[u]) {
      if (seen[e.to]) continue;
      T tmp = dfs(c, e.to);
      if (e.fwd) x[e.id] = tmp;
      else x[e.id] = -tmp;
      res += tmp;
      if (mod2) {
        x[e.id] %= 2;
        if (x[e.id] < 0) x[e.id] += 2;
      }
    }
    if (mod2) res %= 2;
    return res;
  }

  pair<bool, vector<T>> solve(vector<T> &c) {
    x.assign(m, 0);
    seen.assign(n, false);
    rep(u, n) {
      if (seen[u]) continue;
      if (dfs(c, u)) return {false, vector<T>()};
    }
    return {true, move(x)};
  }
};


int main() {
  int n, m; cin >> n >> m;
  vector<P> E;
  V c(n+1);
  rep(i, m) {
    int u, v; cin >> u >> v;
    E.emplace_back(u, v);
    c[u] ^= 1;
  }

  LinearSystemIncidence<int> LSI(n+1, E, true);
  auto sol = LSI.solve(c);

  if (sol.first) {
    rep(i, m) {
      if (sol.second[i]) swap(E[i].first, E[i].second);
      cout << E[i].first << " " << E[i].second << "\n";
    }
  }
  else cout << -1 << "\n";
  return 0;
}

Measured memory_bytes: 11764
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin>>s;
  for(int i=1;i<s.size();i+=2){
    cin>>s.at(i);
    if(s.at(i)=='R'){
      cout<<"No";
      return 0;
    }
  }
  for(int i=0;i<s.size();i+=2){
   if(s.at(i)=='L'){
     cout<<"No";
     return 0;
   }
  }
  cout<<"Yes";
}

Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 1e6 + 10 ;
const ll INF = 1e18 + 10 ;
int s ;
int dp[2005] ;
int dfs(int sum){
    if ( sum == 0 ) {
        return 1 ;
    }
    if ( dp[sum] != -1 ) return dp[sum] ;
    int ans = 0 ;
    for(int i = 3; i <= s; i++){
        if ( sum - i >= 0 ){
            ans += dfs(sum - i) ;
        }
        ans %= MOD ;
    }
    return dp[sum] = ans ;
}
signed main(){
    fastio
    memset(dp, -1, sizeof dp) ;
    cin >> s ;
    int ans = dfs(s) ;
    cout << ans << endl;
    return 0; 
}

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

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

typedef struct{
    int priority;
    double value;
}data;

//昇順
int asc(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}

//降順
int desc(const void* a, const void* b){
    return *(int*)b-*(int*)a;
}

int main(void){
    int N;
    scanf("%d",&N);

    //A[0]~A[N-1]に格納する
    int* A;
    NEW(A,N);
    for(int i=0;i<N;i++){
        scanf("%d",&A[i]);
    }

    long ans=0;
    for(int i=0;i<N;i++) ans+=A[i]-1;
    printf("%ld\n",ans);

    return 0;
}

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

double dp[51][6001];

int main()
{
	int X,Y,Z;
	while(cin >> X >> Y >> Z, (X||Y||Z))
	{
		int V[4];
		for(int i=0; i<X; i++)
			cin >> V[i];

		int E[51]={0},A[51];
		for(int i=0; i<Z; i++)
		{
			int n;
			cin >> n;
			cin >> E[n] >> A[n];
		}

		memset(dp,0,sizeof(dp));
		
		dp[0][0]=1;
		for(int i=0; i<Y; i++)
		for(int j=0; j<=5000; j++)
		{
			for(int k=0; k<X; k++)
			{
				int next=min(i+V[k], Y);
				int gold=j;
				if(E[next]==2) gold+=A[next];
				if(E[next]==3) gold=max(gold-A[next], 0);

				if(E[next]!=1) dp[next][gold]+=dp[i][j]/X;
				else
				{
					int g=min(next+A[next], Y);
					dp[g][j]+=dp[i][j]/X;
				}


			}
		}

		double ans=0;
		for(int i=0; i<=5000; i++)
			ans += 1.0*i*dp[Y][i];

		cout << (int)ans << endl;
	}
}

Measured memory_bytes: 3256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



namespace Test1 {



    class hasi {
        public int c1=-1, c2=-1;
        public bool used = false;
        public int cost = -1;
        public hasi(int c1, int c2, int cost){this.cost = cost; this.c1=c1;this.c2=c2;}
        public int transPortFrom(int start) {
            if (start == c1) { return c2; }
            if (start == c2) { return c1; }
            else { return -1; }
        }

    }

    class city {
        public bool check = false;
         public int id;
        public hasi fromHasi = null;
    }


    class ClassMain {

       

        public static void Main(String[] args) {
            string line;
            while ((line = Console.ReadLine()) != null) {
                int[] nm = line.Split(' ').Select(int.Parse).ToArray();
                if (nm[0] == 0) { break; }
                city[] cities = new city[nm[0]];
                for (int i = 0; cities.Length > i; i++) { 
                    cities[i]= new city();
                    cities[i].id = i; 
                }
                hasi[] hasis = new hasi[nm[1]];

                for (int i = 0; i < nm[1]; i++) {
                    int[] inputs =
                        Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                    hasis[i]=new hasi(inputs[0],inputs[1],inputs[2]);

                }

                doDijkstra(cities, hasis);

                int sumcost = 0;
                for (int i = 0; i < hasis.Length; i++) {
                    if (hasis[i].used) { sumcost += hasis[i].cost; }
                }
                Console.WriteLine(sumcost);
            }
        }


        public static void doDijkstra(city[] cities, hasi[] hasis) {
            cities[0].check = true;
            while (true) {
                //Check.
                int min = int.MaxValue;
                hasi addHashi = null;
                for (int i = 0; i < cities.Length; i++) {
                    city acity = cities[i];
                    if (acity.check == false) { continue; }
                    
                    for (int j = 0; j < hasis.Length; j++) {
                        int transTo = hasis[j].transPortFrom(acity.id);
                        if (transTo < 0) { continue; }
                        if (cities[transTo].check) { continue; }
                        if (hasis[j].cost < min) {
                            min = hasis[j].cost;
                            addHashi = hasis[j];
                        }
                    }
                }
                cities[addHashi.c1].check = true;
                cities[addHashi.c2].check = true;
                addHashi.used = true;

                bool endflg = true;
                for (int i = 0; i < cities.Length; i++) {
                    if(cities[i].check==false){endflg = false;}
                }
                if (endflg) { return; }
            }//endWile
        }//end dijkstra
    }



    
}

Measured memory_bytes: 6124
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

int op(int a, int b) {
    return max(a, b);
}

int e() {
    return -1;
}

int main() {
    int N, K;

    cin >> N >> K;

    vector<int> A(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int max_val = 300000;

    segtree<int, op, e> seg(max_val+1);

    for (int i = 0; i < N; i++) {
        seg.set(A[i], seg.prod(max(0, A[i] - K), min(max_val, A[i] + K) + 1) + 1);
    }

    cout << seg.prod(1, max_val+1)+1 << endl;

    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int ui32;
const long long INFLL = 1e18;

using namespace std;

const int MAXN = 2 * 100000;

ll sum[MAXN + 10], xr[MAXN + 10];
int a[MAXN + 10], nxt[MAXN + 10], n;

ll solve() {
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i - 1];
        xr[i] = xr[i - 1] ^ a[i - 1];
    }

    nxt[n + 1] = n + 1;
    int ptr = n + 1;

    for (int i = n; i >= 1; i--) {
        nxt[i] = ptr;
        if (a[i - 1]) {
            ptr = i;
        }
    }

    ll ans = 0;

    for (int l = 1; l <= n; l++) {
        for (int r = l, cnt = 0; r <= n; r++) {
            if (sum[r] - sum[l - 1] == (xr[r] ^ xr[l - 1])) {
                ++ans;
                if (r + 1 <= n && !a[r]) {
                    ans += nxt[r + 1] - r - 1;
                    r = nxt[r + 1] - 1;
                }
            } else {
                break;
            }
        }
    }

    return ans;
}

ll solve1() {
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i - 1];
        xr[i] = xr[i - 1] ^ a[i - 1];
    }

    nxt[n + 1] = n + 1;
    int ptr = n + 1;

    for (int i = n; i >= 1; i--) {
        nxt[i] = ptr;
        if (a[i - 1]) {
            ptr = i;
        }
    }

    ll ans = 0;

    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            if (sum[r] - sum[l - 1] == (xr[r] ^ xr[l - 1])) {
                ++ans;
            }
        }
    }

    return ans;
}

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

    cin >> n;

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

    cout << solve() << "\n";
    return 0;

    srand(time(NULL));

    for (int t = 0; ; t++) {
        n = rand() % 100 + 1;
        for (int i = 0; i < n; i++) {
            a[i] = rand() % 10;
        }
        int r1 = solve();
        int r2 = solve1();

        cout << r1 << " " << r2 << "\n";
        if (r1 != r2) {
            cout << r1 << " " << r2 << "\n";
            cout << n << "\n";
            for (int i = 0; i < n; i++) {
                cout << a[i] << " ";
            }
            cout << "\n";
            return 0;
        }
    }
    return 0;
}

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

int n;
string s;

int main(){
  cin >> n >> s;
  int res = 0;
  rep(i, n){
    bool right[30], left[30];
    rep(j, 30)right[j] = left[j] = false;
    for(int j = 0; j < i; j++){
      right[s.at(j) - 'a'] = true;
      //cout << s.at(j) - 'a';
      cerr << s.at(j);
    }
    cerr << " ";
    for(int j = i; j < n; j++){
      left[s.at(j) - 'a'] = true;
      cerr << s.at(j);
    }
    cerr << " ";
    int sum = 0;
    rep(j, 30){
      if(right[j] && left[j]){
        sum++;
      }
    }
    cerr << sum << endl;
    res = max(res, sum);
  }
  cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

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

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

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

int main(){
    int h, w; cin>>h>>w;
    vector<string> a(h);
    vector<int> cnt(26, 0);
    for(int i=0; i<h; i++) cin>>a[i];

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cnt[a[i][j]-'a']++;
        }
    }

    bool valid=true;
    int need4=0, need2=0, need1=0;
    if(h%2==0 && w%2==0){
        need4=(h/2)*(w/2);
        for(int i=0; i<26; i++){
            need4-=cnt[i]/4;
            cnt[i]%=4;
            if(cnt[i]!=0) valid=false;
        }
    }
    else if(h%2==0 || w%2==0){
        int even=(h%2==0?h:w);
        need2=even/2;
        need4=(h/2)*(w/2);
        for(int i=0; i<26; i++){
            need4-=cnt[i]/4;
            cnt[i]%=4;
        }

        if(need4<0){
            need2+=2*need4;
            need4=0;
        }

        for(int i=0; i<26; i++){
            need2-=cnt[i]/2;
            cnt[i]%=2;
            if(cnt[i]!=0) valid=false;
        }
    }
    else{
        need1=1;
        need2=(h/2)+(w/2);
        need4=(h/2)*(w/2);
        for(int i=0; i<26; i++){
            need4-=cnt[i]/4;
            cnt[i]%=4;
        }

        if(need4<0){
            need2+=2*need4;
            need4=0;
        }

        for(int i=0; i<26; i++){
            need2-=cnt[i]/2;
            cnt[i]%=2;
            need1-=cnt[i];
        }        
    }
    
    if(valid && need1==0 && need2==0 && need4==0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair <int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;
const char nl = '\n';

void solve() {
    int n;
    cin >> n;
    int ara[n];
    for(int i = 0; i < n; ++i){
        cin >> ara[i];
    }
    sort(ara, ara + n);
    ll a(0), b(0);
    ll len = n - 1;
    char c(1);
    while(len){
        if(ara[len] == ara[len - 1]){
            if(c){
                a = ara[len];
                c = 0;
            }
            else{
                b = ara[len];
                break;
            }
            len--;
        }
        len--;
    }
    cout << a * b << nl;
}

int main() {
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 4052