akhauriyash/Code-Regression huggingface dataset:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=[a[i],i]
a.sort()
a.reverse()
dp=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
  for j in range(n):
    if i+j<=n-1:
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a[i+j][0]*abs(a[i+j][1]-i))
      dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a[i+j][0]*abs(a[i+j][1]-(n-j-1)))
ans=[]
for i in range(n):
  ans.append(dp[i][n-i])
print(max(ans))

Measured memory_bytes: 101884
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def s(n):
        if n < 0:
            return 0
        m = n >> 2
        res = 0
        for i in range(m << 2,n+1):
            res ^= i
        return res
    a,b = LI()
    print(s(a-1)^s(b))
    return

#Solve
if __name__ == "__main__":
    solve()


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

int main() {
    int N, K, KK;
    cin>>N>>K;
    KK=K;
    int ans=0;
    while(true){
        if(KK>N){
            break;
        }
        else{
            KK = KK*K;
            ans++;
        }
    }
    cout<<ans+1<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M 998244353//1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000000
#define N 200005
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int n,k;
   cin>>n>>k;
   int s=0;
   vi a(n);
   rep(i,0,n)cin>>a[i];
   sort(all(a));
   for(int i=0;i<k;i++)
    s+=a[i];
   cout<<s<<endl;

}


Measured memory_bytes: 3656
def dfs(maze, x, y)
  c = maze[y][x]
  return if c == 0

  maze[y][x] = 9

  dfs(maze, x - 1, y) if x > 0 && maze[y][x - 1] == c
  dfs(maze, x, y - 1) if y > 0 && maze[y - 1][x] == c
  dfs(maze, x + 1, y) if maze[y][x + 1] && maze[y][x + 1] == c
  dfs(maze, x, y + 1) if maze[y + 1] && maze[y + 1][x] == c
end

while true
  w, h = gets.split.map(&:to_i)
  break if w == 0 && h == 0

  maze = Array.new(h) {Array.new(w, 0)}

  xs, ys = gets.split.map(&:to_i)
  xg, yg = gets.split.map(&:to_i)

  n = gets.to_i
  n.times do |i|
    c, d, x, y = gets.split.map(&:to_i)
    if d == 0
      xe = x + 3; ye = y + 1
    else
      xe = x + 1; ye = y + 3
    end
    x.upto(xe) do |xt|
      y.upto(ye) do |yt|
        maze[yt - 1][xt - 1] = c
      end
    end
  end

  dfs(maze, xs - 1, ys - 1)
  puts (maze[yg - 1][xg - 1] == 9) ? 'OK' : 'NG'
end

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

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int cnt = 0;
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) cnt++;
    }

    int ans = cnt + k * 2;
    cout << min(ans, n - 1) << endl;
    return 0;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> v(n), p(n), q(n);
    rep(i,n) cin >> p[i];
    rep(i,n) cin >> q[i];
    rep(i,n) v[i] = i+1;
    int cnt = 1, a, b;
    do{
        bool is_a = true, is_b = true;
        rep(i,n){
            if(v[i] != p[i]) is_a = false;
            if(v[i] != q[i]) is_b = false;
        }
        if(is_a) a = cnt;
        if(is_b) b = cnt;
        cnt++;
    }while(next_permutation(v.begin(), v.end()));
    int ans = abs(a - b);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
import java.util.*;
 
public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
      	long[] arr = new long[N];
      	for(int i=0; i<N; i++) arr[i] = sc.nextLong();
      	long[] sumArr = new long[N];
      	long sum = 0;
      
      	long mod = 1000000000 + 7;
      
      for(int i= N-1; i>=0; i--){
        sum = (sum + arr[i])%mod;
        sumArr[i] = sum;
      }
      
      	long res = 0;
      for(int i=0; i<N-1; i++){
        long nextSum = sumArr[i+1];
          res = (res + (arr[i] * nextSum)%mod)%mod;
      }
      	System.out.println(res);
	}
}

Measured memory_bytes: 62340
import java.util.Scanner;

public class Main{

	private static final String UP = "U";
	private static final String DOWN = "D";
	private static final String LEFT = "L";
	private static final String RIGHT = "R";

	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			int sx = sc.nextInt();
			int sy = sc.nextInt();
			int tx = sc.nextInt();
			int ty = sc.nextInt();
			execute(sx, sy, tx, ty);
		};
	}

	private static void execute(int sx,int sy,int tx,int ty) {
		int dx = tx - sx;
		int dy = ty - sy;
		StringBuilder sb = new StringBuilder();
		for(int i = 0 ; i < dy ; i++) {
			sb.append(UP);
		}
		for(int i = 0 ; i < dx ; i++) {
			sb.append(RIGHT);
		}
		for(int i = 0 ; i < dy ; i++) {
			sb.append(DOWN);
		}
		for(int i = 0 ; i < dx ; i++) {
			sb.append(LEFT);
		}
		sb.append(LEFT);
		for(int i = 0 ; i < dy ; i++) {
			sb.append(UP);
		}
		sb.append(UP);
		for(int i = 0 ; i < dx ; i++) {
			sb.append(RIGHT);
		}
		sb.append(RIGHT);
		sb.append(DOWN);
		sb.append(RIGHT);
		for(int i = 0 ; i < dy ; i++) {
			sb.append(DOWN);
		}
		sb.append(DOWN);
		for(int i = 0 ; i < dx ; i++) {
			sb.append(LEFT);
		}
		sb.append(LEFT);
		sb.append(UP);
		System.out.println(sb.toString());
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

#define ALL(x) x.begin(),x.end()
#define get_tp(t,i) get<i>(t)
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<int, vector<int>, greater<int> > gpq; //逆順priority_queue
typedef priority_queue<int> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

int main(){
    char a;
    cin>>a;
    if('A'<=a && a<='Z'){
        cout<<"A"<<endl;
    }else{
        cout<<"a"<<endl;
    }
}

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

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

int main() {
    int N;
    cin >> N;
    map<string, int> m;
    string s;
    REP(i, N){
        cin >> s;
        m[s]++;
    }
    vector<string> ss{"AC", "WA", "TLE", "RE"};
    for (auto tmp: ss){
        cout << tmp << " x " << m[tmp] << endl;
    }

    return 0;
}

Measured memory_bytes: 3228
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include "bits/stdc++.h"
using namespace std;
typedef long long unsigned int ll;

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

int main(){
    string s;
    cin>>s;
    int cnt=0;
    for(int i=0;i<3;i++){
        if(s[i]=='1')
            cnt++;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	#ifdef LOCAL
//		freopen("in1.txt", "r", stdin);
//		freopen("in1.txt", "w", stdout);
	#endif
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	ll ans = LLONG_MIN;
	ans = max(ans, a*c);
	ans = max(ans, a*d);
	ans = max(ans, b*c);
	ans = max(ans, b*d);
	cout << ans << '\n';
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long int
#define INF INT_MAX
#define mod
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main()
{
    chutiyaap;
    int n;cin>>n;
    cout<<pow(n,3);
    return 0;
}

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

using namespace std;

int main () {
    int N,W;
    cin >> N >> W;
    vector <long long>w(N);
    vector <long long>v(N);
    for (int i = 0 ; i < N ; i++)
    {
        cin >> w[i] >> v[i];
    }
    vector <vector <long long> >dp(N + 1, vector<long long>(W + 1, 0));

    for (int i = 0 ; i < N ; i++)
    {
        for (int j = 0 ; j <= W ; j++) {
            dp[i + 1][j] = w[i] <= j ? max(dp[i][j - w[i]] + v[i], dp[i][j]) : dp[i][j];
        }
    }
    cout << dp[N][W] <<endl;
}


Measured memory_bytes: 80256
N = int(input())
A = [[] for i in range(N)]
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a

d = [[0] * N for i in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if A[i][j] == A[i][k] + A[k][j] and i != k and j != k:
                d[i][j] = 1

ans = 0
for i in range(N):
    for j in range(N):
        if d[i][j] == 0:
            ans += A[i][j]

print(ans // 2)


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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    int A, B, C;
    A = a.size();
    B = b.size();
    C = c.size();

    int res = IINF;
    int MID = 10000;
    // xy[i + MID] は xに比べてyがiだけ後ろにずれているときに正しくマッチするのか
    vector<bool> ab(MID*2, true);
    vector<bool> bc(MID*2, true);
    vector<bool> ac(MID*2, true);

    FOR(i, -B, A) {
        REP(j, A) {
            if(0 <= j - i && j - i < B) {
                bool p = a[j] == b[j - i] || a[j] == '?' || b[j - i] == '?';
                ab[i + MID] = ab[i + MID] && p;
            }
        }
    }
    FOR(i, -C, B) {
        REP(j, B) {
            if(0 <= j - i && j - i < C) {
                bool p = b[j] == c[j - i] || b[j] == '?' || c[j - i] == '?';
                bc[i + MID] = bc[i + MID] && p;
            }
        }
    }
    FOR(i, -C, A) {
        REP(j, A) {
            if(0 <= j - i && j - i < C) {
                bool p = a[j] == c[j - i] || a[j] == '?' || c[j - i] == '?';
                ac[i + MID] =ac[i + MID] && p;
            }
        }
    }

    FOR(i, -B - C, A + C) {
        FOR(j, -B - C, A + B) {
            if(ab[i + MID] && ac[j + MID] && bc[j - i + MID]) {
                int r = max({A, i + B, j + C});
                int l = min({0, i, j});
                int width = r - l;
                res = min(res, width);
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		n: usize,
		_z: isize,
		w: isize,
		a: [isize; n],
	}

	if n == 1 {
		println!("{}", (a[n-1]-w).abs());
	}
	else {
		println!("{}", max((a[n-1]-w).abs(), (a[n-2]-a[n-1]).abs()));
	}
}



Measured memory_bytes: 2180
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#define pi 3.141592653589
#include<iomanip>
using namespace std;
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 1e9
#define LINF 1e17
#define ll long long
#define MOD (int)(1e9+7)

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



int main(){
    
    int flag[1000]={};
    string s;
    
    cin>>s;
    rep(i,0,s.size()){
        if(flag[s[i]]){
            cout<<"no"<<endl;
            return 0;
        }
        else flag[s[i]]=1;
    }
    cout<<"yes"<<endl;
        
    return 0;
}

Measured memory_bytes: 256
from bisect import bisect

def sieve(n):
  num = [True]*n
  num[0] = num[1] = False
  for i in xrange(2,int(n**0.5)+1):
    if num[i]:
      for j in xrange(i**2, n, i):
        num[j] = False
  return [i for i in xrange(2,n) if num[i]]

prime = sieve(999999)

while True:
  try:
    print bisect(prime, input())
  except:
    break

Measured memory_bytes: 14588
#include <iostream>
using namespace std;
#define mod 998244353
#define int long long int
int power(int a, int b)
{
    int res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % mod;
        b = b / 2;
        a = (a * a) % mod;
    }
    return res;
}
signed main()
{
    int n, m, k;
    cin >> n >> m >> k;
    int fact[n + 1], factinv[n + 1];
    fact[0] = 1, factinv[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        fact[i] = (fact[i - 1] * i) % mod;
        factinv[i] = power(fact[i], mod - 2);
    }
    int ans = 0;
    for (int i = 0; i <= k; i++)
    {
        ans = (ans + ((((((((fact[n - 1] * factinv[n - i - 1]) % mod) * factinv[i]) % mod) * m) % mod) * power(m - 1, n - i - 1)) % mod) % mod) % mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6700
//Never stop trying
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

#define dbg(x) cerr << " - " << #x << " : " << x << endl;
#define dbgs(x,y) cerr << " - " << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << " - " << #v << " : " << endl << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;

void IO() {
#ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
#endif
}


int32_t main() {
   boost; IO();

   int K; cin>>K;
   int x=0;
   FOR(i,0,1e7){
      x*=10; x+=7; x%=K;
      if(x==0){cout << i+1 << endl; return 0;}
   }
   cout << -1 << endl;



   return 0;
}

/* Careful!!!
   .Array bounds
   .Infinite loops
   .Uninitialized variables / empty containers
   .Order of input

   Some insights:
   .Binary search
   .Graph representation
   .Write brute force code
   .Change your approach
*/


Measured memory_bytes: 3620
N = int(input())

i = 2
tmp = N

ans = 0
while i*i <= N:
    cnt = 0
    while tmp % i == 0:
        tmp //= i
        cnt += 1
    if cnt > 0:
        k = 1
        while cnt - k >= 0:
            cnt -= k
            ans += 1
            k += 1
    i += 1
if tmp != 1:
    ans += 1

print(ans)

Measured memory_bytes: 9144
#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<cstring>
using namespace std;

int main()
{
	int a[3];
	for (int i = 0; i < 3; i++)
		cin >> a[i];
	sort(a, a + 3, greater<int>());
	cout << 10 * a[0] + a[1] + a[2] << endl;

}

Measured memory_bytes: 256
//By Vlgd
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int L[N],A[N],n;
int lis(){
	L[0]=A[0];
	int len=1;
	for(int i=1;i<n;i++){
		if(A[i]>L[len-1]) L[len++]=A[i];
		else *lower_bound(L,L+len,A[i])=A[i];
	}
	return len;
}
//low eff
/*
int lis(){
	L[0]=0;
	A[0]=0;
	int k,ans=-100;
	for(int i=1;i<=n;i++){
		k=0;
		for(int j=0;j<i;j++)
			if(A[j]<A[i]&&L[j]>L[k]) k=j;
		L[i]=L[k]+1;
		ans=max(L[i],ans);
	}
	return ans; 
} */
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	printf("%d\n",lis());
	return 0;
}


Measured memory_bytes: 3892
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MN 200005
using namespace std;
typedef long long ll;
ll ans;
bool used[MN];
int n,m,fa[MN],id[MN],a[MN],sz[MN];
int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
bool cmp(int x,int y){return a[x]<a[y];}
int main(){
	scanf("%d%d",&n,&m);int tt=(n-1-m)*2;int x,y;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),fa[i]=id[i]=i;sort(id+1,id+n+1,cmp);
	for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),fa[getf(++x)]=getf(++y);
	
	for(int i=1;i<=n&&tt;i++)if(!used[id[i]]){
		if(sz[getf(id[i])])continue;
		sz[getf(id[i])]++,used[id[i]]=1,--tt,ans+=a[id[i]];
	}
	for(int i=1;i<=n&&tt;i++)if(!used[id[i]]){
		if(sz[getf(id[i])]+1>n-1-m)continue;
		sz[getf(id[i])]++,--tt,ans+=a[id[i]];
	}if(tt)puts("Impossible");else printf("%lld\n",ans);
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main()
{
	char test1[100],test2[100],test3[100],test4[1];
	int num1=0;
	
	cin>>test1>>test2>>test3;
	num1=strlen(test2);
	test2[0]=toupper(test2[0]);
	cout<<'A'<< test2[0] <<"C\n";
	return 0;
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	int h, w;
	cin >> h >> w;
	vector<int> cnt(26, 0);
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			char c;
			cin >> c;
			cnt[c-'a']++;
		}
	}

	int g4=(h/2)*(w/2), g2=h/2+w/2, g1=1;
	if(h%2==0){
		g2-=w/2;
		g1--;
	}
	if(w%2==0){
		g2-=h/2;
		g1--;
	}
	if(g1<0) g1=0;

	for(int i=0; i<g4; i++){
		for(int j=0; j<26; j++){
			if(cnt[j]>=4){
				cnt[j]-=4;
				break;
			}
		}
	}

	for(int i=0; i<g2; i++){
		for(int j=0; j<26; j++){
			if(cnt[j]>=2){
				cnt[j]-=2;
				break;
			}
		}
	}

	for(int i=0; i<g1; i++){
		for(int j=0; j<26; j++){
			if(cnt[j]>=1){
				cnt[j]-=1;
				break;
			}
		}
	}

	for(int i=0; i<26; i++){
		if(cnt[i]>0){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**

 *
 * @author Abhijeetkns
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ADoubleHelix solver = new ADoubleHelix();
        solver.solve(1, in, out);
        out.close();
    }

    static class ADoubleHelix {
        public void solve(int testNumber, Scanner in, PrintWriter out) {

            String s = in.next();
            if (s.compareTo("A") == 0)
                out.println("T");
            else if (s.compareTo("T") == 0)
                out.println("A");
            else if (s.compareTo("G") == 0)
                out.println("C");
            else out.println("G");

        }

    }
}



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

static const int MAX = 10000001;
bool isPrime[MAX];
 
void aryPrime() {
  for (int i = 0; i < MAX; i++) isPrime[i] = true;
  isPrime[0] = false;
  isPrime[1] = false;
  int n = sqrt(MAX);
  for (int i = 2; i <= n; i++) {
    if (!isPrime[i]) continue;
    for (int j = i * 2; j < MAX; j += i) {
      isPrime[j] = false;
    }
  }
}

// 最大公約数
ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

int main() {
  ll A, B;
  cin >> A >> B;
  ll m = min(A, B);
  int cnt = 1;
  aryPrime();
  ll g = gcd(A, B);
  ll t = g;
  for (ll i = 2; i * i <= t; i++) {
    if (g % i == 0) cnt++;
    while (g % i == 0) {
      g /= i;
    }
  }
  if (g != 1) cnt++;
  cout << cnt << "\n";

  return 0;
}

Measured memory_bytes: 9984
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  map<string, int> m;
  for(int i = 0; i < n; i++){
    string s;
    cin >> s;
    m[s] = 1;
  }
  int cnt = 0;
  for(auto p : m) {
    if(p.second > 0){
      cnt++;
    }
  }
  cout << cnt << endl;

  return 0;
}

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

a.sort()

a2 = []
for i, x in enumerate(a):
  a2.append((x, i))

from math import factorial


def c(n, r):
  if n - r < 0:
    return 0
  return factorial(n) // factorial(r) // factorial(n - r)


MOD = 10**9 + 7  # 出力の制限

# https://qiita.com/derodero24/items/91b6468e66923a87f39f


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


g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, n + 1):
  g1.append((g1[-1] * i) % MOD)
  inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
  g2.append((g2[-1] * inverse[-1]) % MOD)


ma = 0
mi = 0
for i in range(n):
  ma += a[i] * cmb(i, k - 1)
  mi += a[i] * cmb(n - i - 1, k - 1)

print((ma - mi) % MOD)


Measured memory_bytes: 31948
S = gets.chomp
Qn = gets.to_i
Q = readlines.map(&:split)

reversed = false
prefix = ''
suffix = ''

Q.each do |t,f,c|
  case t
  when '1'
    reversed ^= true
    prefix, suffix = suffix, prefix
  when '2'
    if reversed
      f == '1' ? prefix.concat(c) : suffix.insert(0, c)
    else
      f == '1' ? prefix.insert(0, c) : suffix.concat(c)
    end
  end
end
if reversed
  S.reverse!
  prefix.reverse!
  suffix.reverse!
end
puts prefix + S + suffix


Measured memory_bytes: 57056
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(_,v.size()){rep(__,v[_].size())cout<<" "<<v[_][__];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 1e18+10 : 1e9+10;
// int dx[]={0,1,0,-1,1,1,-1,-1};
// int dy[]={1,0,-1,0,1,-1,1,-1};//RDLU
int dx[]={-1,-1,0,0,1,1};
int dy[]={-1,0,-1,1,0,1};//RDLU
int main(){
	int n;
	double d,x,sum=0;
	cin>>n>>d>>x;
	while(n){
		sum+=d+(2*n-1)*x/2;
		d+=(2*d+5*x)/2/n;
		x+=2*x/n;
		n--;
	}
	cout<<shosu(9)<<sum<<endl;
}







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

int main(){

    int N, W;
    cin >> N >> W;
    vector<long long> w(N), v(N);
    for(int i = 0; i < N; i++) cin >> w[i] >> v[i];

    vector<vector<long long> > dp(N + 1, vector<long long>(W + 1, 0));

    for(int i = 0; i < N; i++){
        for(int j = 0; j <= W; j++){

            if(w[i] <= j) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
        }
    }    

    cout << dp[N][W] << endl;

    return 0;
}

Measured memory_bytes: 80256
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
#define repn(i,s,n) for (int i=int(s); i < int(n); i++)
#define rep(i,n) repn(i,0,n)
#define repd(i,n) for (int i=int(n)-1; i >= 0; i--)


struct Node {
  int val;  // この区間に足される値
  int min;  // この区間の最小値（valを含む）
  Node() : min(0), val(0) {}
};

#define LC(k) (k * 2 + 1)  // 左の子
#define RC(k) (k * 2 + 2)  // 右の子

const int INF = INT_MAX;

struct RMQRangeAddSegTree {
  vector<Node> tree;
  int n;
  RMQRangeAddSegTree(int n) : n(n), tree(n*2 - 1) {}  // nは2のべき乗とする

  void addRange(int l, int r, int val) {
    addRange(l, r, 0, 0, n, val);
  }

  int minRange(int l, int r) {
    return minRange(l, r, 0, 0, n);
  }

  // a,b: クエリ対象の範囲[a,b)
  // k: 現在のノードの番号
  // l,r: 現在のノードkの範囲[l,r)
  // val: [a,b)に追加する値
  void addRange(int a, int b, int k, int l, int r, int val) {
      if (r <= a || b <= l) return;
      process_lazy(k);
      if (a <= l && r <= b) {
        tree[k].val += val;
      }
      else {
        addRange(a, b, LC(k), l, (l + r) / 2, val);
        addRange(a, b, RC(k), (l + r) / 2, r, val);
      }
      update_node(k);
  }

  int minRange(int a, int b, int k, int l, int r) {
      if (r <= a || b <= l) return INT_MAX;
      process_lazy(k);
      if (a <= l && r <= b) {
        return tree[k].min;
      }
      int lmin = minRange(a, b, LC(k), l, (l + r) / 2);
      int rmin = minRange(a, b, RC(k), (l + r) / 2, r);
      return min(lmin, rmin);
  }

  // 頂点情報の更新。葉ノード側の更新を上へ伝搬していく
  // この処理の後、ノードkのもつ各値（ここではmin）は正しいものとなる
  void update_node(int k) {
    if (k < n - 1) {  // k は葉でない
      tree[k].min = tree[k].val + min(tree[LC(k)].min, tree[RC(k)].min);
    }
    else {  // k は葉
      tree[k].min = tree[k].val;
    }
  }

  // 遅延評価の実行。根ノード側の更新分を下へ伝搬していく
  // この処理の後、ノードkのもつ各値（ここではmin）は正しいものとなる
  void process_lazy(int k) {
    if (k < n - 1 && tree[k].val != 0) {
      tree[LC(k)].val += tree[k].val;
      tree[RC(k)].val += tree[k].val;
      tree[LC(k)].min += tree[k].val;
      tree[RC(k)].min += tree[k].val;
      tree[k].val = 0;
    }
  }
};

int main() {

  int n, q;
  cin >> n >> q;
  int nPow2 = n-1;
  nPow2 |= nPow2 >> 1;
  nPow2 |= nPow2 >> 2;
  nPow2 |= nPow2 >> 4;
  nPow2 |= nPow2 >> 8;
  nPow2 |= nPow2 >> 16;
  nPow2++;

  RMQRangeAddSegTree segtree(nPow2);
  segtree.addRange(0, n, INF);
  rep(qi, q) {
    int com, x, y;
    cin >> com >> x >> y;
    if (com == 0) {
      // update(x,y)
      int origval = segtree.minRange(x, x+1);
      segtree.addRange(x, x+1, -origval + y);
    }
    else {
      // find(x,y)
      cout << segtree.minRange(x, y+1) << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3120
#include <algorithm>
#include <cstdio>
#include <bitset>

const int N = 300;
const int MOD = 998244353;

using Bitset = std::bitset<N>;

int n, m, two[N + 1];
Bitset mat[N];

int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++ i) {
    for (int j = 0, a; j < m; ++ j) {
      scanf("%d", &a);
      if (a == 1) {
        mat[i].set(j);
      }
    }
  }
  int rank = 0;
  for (int j = 0; j < m; ++ j) {
    int pivot = rank;
    while (pivot < n && !mat[pivot].test(j)) {
      pivot ++;
    }
    if (pivot == n) {
      continue;
    }
    std::swap(mat[rank], mat[pivot]);
    for (int i = rank + 1; i < n; ++ i) {
      if (mat[i].test(j)) {
        mat[i] ^= mat[rank];
      }
    }
    rank ++;
  }
  two[0] = 1;
  for (int i = 1; i <= N; ++ i) {
    two[i] = two[i - 1] * 2 % MOD;
  }
  int result = 1LL * (two[n] + MOD - two[n - rank]) * two[m - 1] % MOD;
  printf("%d\n", result);
}


Measured memory_bytes: 256
//g++ -std=gnu++14 a.cpp
//#include <bits/stdc++.h>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main(){
   ll H,A;
   cin >> H >> A;
   if(H%A == 0){
     cout << H/A << endl;
   }else{
     cout << H/A + 1 << endl;
   }


}


Measured memory_bytes: 3636
k=int(input())
from collections import deque
l=deque([1,2,3,4,5,6,7,8,9])
a=0
for _ in range(k):
  a=l.popleft()
  if a%10==0:
    l.append(a*10)
    l.append(a*10+1)
  elif a%10==9:
    l.append(a*10+8)
    l.append(a*10+9)
  else:
    l.append(a*10+a%10-1)
    l.append(a*10+a%10)
    l.append(a*10+a%10+1)
print(a)
    


Measured memory_bytes: 11940
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>

long long int power(long long int base, int exp, int mod) {
	switch (exp) {
	case 0: return 1L;
	case 1: return base % mod;
	default: return power(base * base % mod, exp / 2, mod) * power(base, exp % 2, mod) % mod;
	}
}
int main() {
	int n, k, m; std::cin >> n >> k >> m;
	std::vector<std::vector<long long int>> count(1 << (k * 2), std::vector<long long int>(k, 0));
	for (auto i = 0; i < k; ++i) count[0][i]++;
	long long int result = 0;
	for (auto p = 0; p < count.size(); ++p) {
		int length = 1;
		for (auto i = 0; i < 2 * k; ++i) {
			if (((1 << i) & p) != 0) ++length;
		}
		if (length >= n) continue;
		long long int bug_sum = 0;
		for (auto i = 0; i < k; ++i) if (count[p][i] != 0) {
			count[p][i] %= m;
			for (auto j = 0; j < k; ++j) {
				if ((1 << (i + k - j) & p) == 0) {
					count[(1 << (i + k - j)) | p][j] += count[p][i];
				}
				else {
					bug_sum += count[p][i];
				}
			}
		}
		result += bug_sum % m * power(k, n - length - 1, m) % m;
		result %= m;
	}
	std::cout << result << '\n';
}


Measured memory_bytes: 125628
N, K = map(int, input().split())
S = input()
left = 0
rc = 0
rf = False
lf = False
ans = 0
if set(S) == set("0") or set(S) == set("1"):
    print(len(S))
    exit()
for right in range(N):
    if rf and S[right] == "0" and rc <= K:
        if right != N-1:
            continue
        else:
            ans = max(ans, right - left)
            break
    if S[right] == "1":
        rf = False
    if S[right] == "0":
        rc += 1
        rf = True
    if rc > K:
        while True:
            if S[left] == "1":
                left += 1
            if S[left] == "0":
                while S[left] == "0":
                    left += 1
                break
        rc -= 1
    ans = max(ans, right - left)
print(ans+1)


Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <vector>
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;
int t = 0;

void visit(int u, int *color, int *d, int *f, vector<vector<int>> Adj){
    int zero = 0;
    color[u] = GRAY;
    d[u] = ++t;
    for (int i = 1; i <= Adj[u].size(); i++){
        if (Adj[u][i] == 0){
            break;
        }
        if (color[Adj[u][i]] == WHITE){
            visit(Adj[u][i], color, d, f, Adj);
        }
    }
    color[u] = BLACK;
    f[u] = ++t;
}

int main(int argc, char* argv[]) {
    int n, u, k, v;
    cin >> n;
    n++;
    int color[n], d[n], f[n];
    vector<vector<int>> Adj(n, vector<int>(n, 0));

    for (int i = 1; i <= n; i++) color[i] = WHITE;

    for (int i = 1; i < n; i++){
        cin >> u >> k;
        for (int j = 1; j <= k; j++){
            cin >> v;
            Adj[i][j] = v;
        }
    }

    for (int i = 1; i < n; i++)
        if (color[i] == WHITE)
            visit(i, color, d, f, Adj);

    for (int i = 1; i < n; i++){
        printf("%d %d %d\n", i, d[i], f[i]);
    }
    return 0;
}



Measured memory_bytes: 7344
#include <sstream>
#include <iostream>
#include <string>
 
using namespace std;
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef long long LL;
 
string FB(LL n){
    string ret="";
    if(n%3==0)ret+="Fizz";
    if(n%5==0)ret+="Buzz";
    if(ret == "")ret = toString(n);
    return ret;
}
 
bool is10(LL q){
    bool flag = true;
    while(q>=10){
        if(q%10)flag = false;
        q/=10;
    }
    if(q!=1)flag = false;
    return flag;
}
 
LL m10(LL q){
    LL ret = 1;
    while(ret <= q)ret*=10;
    return ret/10;
}
 
 
LL M10(LL q){
    LL ret = 1;
    while(ret < q)ret*=10;
    return ret;
}
 
LL len(LL s, LL e){//[s,e)の文字数
    LL ret;
    if(s >= e)return 0LL;
    if(!is10(s))return len(m10(s), e)-len(m10(s), s);
    if(s*10 < e){
        return len(s, s*10) + len(s*10, e);
    }else{
        int digit = 1;
        LL tmp = s;
        while(tmp>=10){
            digit++;
            tmp/=10;
        }
        LL d3, d5,d15;
        d3 = (e-1)/3-(s-1)/3;
        d5 = (e-1)/5-(s-1)/5;
        d15 = (e-1)/15-(s-1)/15;
        return (e-s-d3-d5+d15)*digit+(d3+d5)*4;
    }
}

int main(){
    LL n;
    string ret = "";
    cin >> n;
    //2文探索-1
    LL l=1, u=2;
    while(len(1,u)<n)u*=2;
    //2分探索-2
    while(u-l>1){
        LL mid = (l+u)/2;
        if(len(1, mid)<n)l = mid;
        else u = mid;
    }
	LL tmp = l;
	while(ret.length()<100)ret+=FB(tmp++);
	cout << ret.substr(n-len(1,l)-1, 20) << endl;
    return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>;
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
 
 
 int main(){
  ll d,t, s ; cin>>d>>t>>s ;
  if(d<=t*s) cout<<"Yes"<<endl ;
  else cout<<"No"<<endl ;
   return 0 ;
 }



Measured memory_bytes: 3628
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

double table[100][100];


int main(){
	int n, m ;
	while(cin >> n >> m , n){
		rep(i,n)rep(j,n)cin >> table[i][j];
		
		long double dp[100][100] = {{0.0}};
		
		rep(i,n)dp[0][i] = 1.0;
		
		rep(i,m-1){ // kaisu 
			rep(j,n){ // chokuzen 
				rep(k,n){ // current
					dp[i+1][k] = max(dp[i+1][k] , dp[i][j] * table[j][k]);
				}
			}
		}
		long double ret = 0;
		rep(i,n){
			ret = max(ret,dp[m-1][i]);
		}
		//long long out = (ret * 100.0);
		//printf("%.2Lf\n",out/100.0);
		printf("%.2Lf\n",ret);
	}
}

Measured memory_bytes: 0
#include<string>
#include<iostream>

int main(){
  float D, T, S;
  std::cin >> D >> T >> S;
  float time = D/S;
  if(time<=T){
    std::cout << "Yes" << std::endl;
  }
  else{
    std::cout << "No" << std::endl;
  }
  return 0;
}

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

using namespace std;

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

    int L=1,R=N;

    for(int i=0;i<M;i++)
    {
        int Li,Ri;
        cin >> Li >> Ri;

        if(Li > L) L=Li;
        if(Ri < R) R=Ri;
    }

    int answer = R - L + 1;

    if(answer > 0) cout << answer << endl;
    else cout << '0' << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
    int n;
    cin >> n;
    vl a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    ll ans = 0;
    rep(i, n-1) ans += a[i];
    ans += a.back()/2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import math

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
maxA = A[len(A)-1]
valid = [True] * (maxA+1)

for i in range(len(A)):
    if valid[A[i]] == False:
        continue
    if i != 0 and A[i-1] == A[i]:
        valid[A[i]] = False
    else:
        for j in range(A[i]*2, maxA+1, A[i]):
            valid[j] = False

count = 0
for i in range(len(A)):
    if valid[A[i]] == True:
        count += 1
print(count)


Measured memory_bytes: 32384
#include <iostream>

using namespace std;

int main(){
	int a,b,c,x;
	cin >> a >> b >> c;
	if(a<1||b<1||c<1||a>10000||b>10000||c>10000){
		cout <<"error."<< endl;
		return 0;
	}
	if(a>b){
		x=a;
		a=b;
		b=x;
		x=0;
	}
	if(b>c){
		x=b;
		b=c;
		c=x;
		x=0;
	}
	if(a>b){
		x=a;
		a=b;
		b=x;
		x=0;
	}
	cout <<a<<' '<<b<<' '<<c<< endl;
	return 0;
}

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

int main(){
  int n,t,min=99999999,cnt=0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&t);
    if(min>t){
      min=t;
      cnt++;
    }
  }
  printf("%d",cnt);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
using namespace std;
using ll = unsigned long long;
using p = pair<int, int>;

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

    vector<p> way(M);

    rep(i, 0, M)
    {
        int a, b;
        cin >> a >> b;
        p pin(a, b);
        way[i] = pin;
    }

    vector<int> root(N);
    rep(i, 0, N)
    {
        root[i] = i + 1;
    }

    int count = 0;

    do
    {
        // 「1」スタートでない順列は条件外
        if (root[0] != 1)
        {
            continue;
        }

        bool clear = true;
        rep(i, 0, N - 1)
        {
            bool go = false;
            const int start = root[i];
            const int end = root[i + 1];
            rep(j, 0, M)
            {
                if (start == way[j].first && end == way[j].second)
                {
                    go = true;
                    break;
                }

                if (start == way[j].second && end == way[j].first)
                {
                    go = true;
                    break;
                }
            }

            if (!go)
            {
                clear = false;
                break;
            }
        }

        if (clear)
        {
            ++count;
        }

    } while (next_permutation(root.begin(), root.end()));

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3536
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

P dp[(1 << 18)];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vi a(1 << n);
    rep(i,(1 << n)){
        cin >> a[i];
    }
    dp[0] = P(0, -1);
    for(int i=1;i<(1<<n);i++){
        int mx1 = i, mx2 = -1;
        rep(j,n){
            if((i >> j) & 1){
                int cri = (i^(1 << j));
                vi vec;
                if(mx1 >= 0){
                    vec.pb(mx1);
                }
                if(mx2 >= 0){
                    vec.pb(mx2);
                }
                if(dp[cri].fi >= 0){
                    vec.pb(dp[cri].fi);
                }
                if(dp[cri].se >= 0){
                    vec.pb(dp[cri].se);
                }
                zip(vec);
                sort(all(vec),[&](int p, int q){
                    return a[p] > a[q];
                });
                mx1 = vec[0], mx2 = vec[1];
            }
        }
        dp[i] = P(mx1, mx2);
    }
    int prv = 0;
    for(int i=1;i<(1<<n);i++){
        cmx(prv,a[dp[i].fi]+a[dp[i].se]);
        cout << prv << "\n";
    }
    return 0;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,X,sum=0;
  cin>>N>>X;
  int M[N];
  for(int i=0;i<N;i++){
    cin>>M[i];
    sum+=M[i];
  }
  sort(M,M+N);
  cout<<N+(X-sum)/M[0]<<endl;
}

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

#define fi first
#define se second
#define pb push_back
#define int long long
#define all(x) (x).begin(), (x).end()

using LL = long long;
using LD = long double;
using pii = pair<int, int>;
using vii = vector<pii>;

const int INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;

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

	int n;
	cin >> n;

	vector<int> a(n);
	for (int& i: a) cin >> i;

	int ans = 0, curr = 0;
	for (int i = 1; i < n; i++) {
		if (a[i] > a[i - 1]) {
			ans = max(ans, curr);
			curr = 0; 
		} else {
			curr++;
		}
	}

	cout << max(ans, curr) << "\n";
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i,k,n) for (ll i = k; i < n; ++i)
#define inputar(a,n) ll a[n];rep(i,0,n)cin>>a[i]
#define PI 3.14159265
const int MOD=1e9+7;


#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a)  (a).begin(),(a).end()

#define test4(x,y,z,a) cerr<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cerr<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cerr<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cerr<<"x is "<<x<<endl;

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

int main()
{
    IOS;
    string s,s1="",s2="";
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(i%2==0) s1+='0';
        else s1+='1';
    }
    for(int i=0;i<s.size();i++)
    {
        if(i%2==1) s2+='0';
        else s2+='1';
    }
    ll mx=s.size();
    ll c=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=s1[i]) c++;
    }
    mx=min(mx,c);
    c=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=s2[i]) c++;
    }
    mx=min(mx,c);
    cout<<mx<<endl;
}

Measured memory_bytes: 720
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc170_b
{
    class Program
    {
        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            string[] strs = line.Split(' ');
            int X = int.Parse(strs[0]);
            int Y = int.Parse(strs[1]);

            if (Y >= X*2 && Y <= X*4 && Y % 2 == 0)
            {
                Console.WriteLine("Yes");
            }

            else
            {
                Console.WriteLine("No");
            }

            Console.Read();
        }
    }
}


Measured memory_bytes: 27516