akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <random> 
#include <vector>
#include <climits>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define ID(x,y) (((x)-1) * m + (y))
#define CL clear
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define low_bit(x) ((x)&(-(x)))
#define dmp(x) cerr<<#x<<"="<<x<<"\n"  
#define MIN(a,b,c) min(a,min(b,c))
#define MAX(a,b,c) max(a,max(b,c))
#define SZ(x) ((int)(x.size())) 
#define sc scanf
#define pf printf
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)

#define int long long

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;

const int N = (int)1e6+10;
const int mod = 1e9+7;
const int inf = 1e9;
const double eps = 1e-16;
const double pi = acos(-1);


inline int rd() {
  int p=0; int f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f*=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}

struct node{int a,b,c,d;}p[N]; int n,m,q;
int a[12]; int ans = 0;
void dfs(int x) {
  if(x==n+1) {
  	int s = 0;
  	rep(i,0,q-1) if(a[p[i].b] - a[p[i].a] == p[i].c) s+=p[i].d;
  	ans = max(ans , s);
  }
  else {
  	rep(i,a[x-1],m) a[x] = i,dfs(x+1);
  }
}
signed main() {
  // freopen("a.in","r",stdin);
  // freopen("a.out","w",stdout);
  n=rd(); m=rd(); q=rd();
  rep(i,0,q-1) p[i].a=rd(),p[i].b=rd(),p[i].c=rd(),p[i].d=rd(); ans = 0;
  a[0] = 1;dfs(1);
  return printf("%lld\n",ans),0;
}

/*
*/


Measured memory_bytes: 3724
fun main(arr:Array<String>) {
    val n = readLine()!!.toInt()
    val lists = (1..3).map { readLine()!!.split(" ").map { it.toLong() }.sorted() }
    val solve = Solve(lists[0], lists[1], lists[2])
    println(solve.getAns())
}

class Solve(val aList:List<Long>, val bList:List<Long>, val cList:List<Long>) {
    fun getAns():Long {
        for(i in cList.indices) {
            getC(i)
        }
        return cList.indices.map { getC(it) }.sum()
    }
    val countCDic = mutableMapOf<Int, Int>()
    val totalCDic = mutableMapOf<Int, Long>()
    val countBDic = mutableMapOf<Int, Int>()
    fun getC(index:Int):Long {
        totalCDic[index]?.let { return it }
        val start = countCDic[index-1]?:0
        var total = totalCDic[index-1]?:0
        var count = start
        for(i in (start..bList.lastIndex)) {
            if(bList[i] >= cList[index]) {
                break
            }
            count = i + 1
            total += getB(i)
        }
        countCDic[index] = count
        totalCDic[index] = total
        return total
    }
    fun getB(index:Int):Int {
        val start = countBDic[index-1]?:0
        var cnt = start
        for(i in (start..aList.lastIndex)) {
            if(aList[i] >= bList[index]) {
                break
            }
            cnt = i + 1
        }
        countBDic[index] = cnt
        return cnt
    }
}

Measured memory_bytes: 127348
#include"iostream"
#include"stdio.h"
using namespace std;
char s[15];
int main()
{
	#ifdef whlzy
	freopen("text.in","r",stdin);
	#endif
	scanf("%s",s);
	if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I')
	printf("Yes");
	else
	printf("No");
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <stdio.h>
#include <string.h>
using ll = long long;

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
using namespace std;

int N;
char S[100000][11];
string str[100000];

signed main()
{
	cin >> N;
	REP(i, N) cin >> S[i];

	REP(i, N)
	{
		ARY_SORT(S[i], 10);
		str[i] = string(S[i]);
	}

	ARY_SORT(str, N);

	int ans = 0;

	string cur = str[0];
	int cnt = 1;
	for (int i = 1; i < N; i++)
	{
		if (cur != str[i])
		{
			if (cnt >= 2)
			{
				ans += (((cnt - 1) + 1) * (cnt - 1)) / 2;
			}
			cnt = 1;
			cur = str[i];
		}
		else
		{
			cnt++;
		}
	}
	if (cnt >= 2)
	{
		ans += (((cnt - 1) + 1) * (cnt - 1)) / 2;
	}

	cout << ans << endl;
}











Measured memory_bytes: 6784
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (sortBy)

main :: IO ()
main = do
  (n : m : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  as <- sortBy (flip compare) . map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    a0 = head as :: Int
    countAndSumGE :: Int -> (Int, Int)
    countAndSumGE k = fst . fst . foldr step (((0, 0), (0, 0)), as) $ as
      where
        step :: Int -> (((Int, Int), (Int, Int)), [Int]) -> (((Int, Int), (Int, Int)), [Int])
        step x (((c, s), (d, t)), ys) = (((c + c', s + s'), (d', t')), sf)
          where
            (pf, sf) = span (k - x <=) ys
            (u, v) = ((,) <$> length <*> sum) pf
            d' = d + u
            c' = d'
            t' = t + v
            s' = x * d' + t'
    countGE :: Int -> Int
    countGE k = fst . fst . foldr step ((0, 0), as) $ as
      where
        step x ((c, d), ys) = ((c + d', d'), sf)
          where
            (pf, sf) = span (k - x <=) ys
            d' = d + length pf
    k = unsafeBinaryMaxInt ((m <=) . countGE) (2, 2 * a0) :: Int
    (c, s) = countAndSumGE (succ k)
  print $ s + k * (m - c)

unsafeBinaryMaxInt :: (Int -> Bool) -> (Int, Int) -> Int
unsafeBinaryMaxInt p = check
  where
    check :: (Int, Int) -> Int
    check ij@(i, j) | p j       = j
                    | otherwise = search ij
    search :: (Int, Int) -> Int
    search = fst . until ((==) <$> succ . fst <*> snd) halve
      where
        halve (i, j) | p m       = (m, j)
                     | otherwise = (i, m)
          where
            m = (i + j) `div` 2

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 58748
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
#define debug(var) cout << "[" << #var << "] " << var << endl
const ll mod = 1000000007;
 
int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i, n) cin >> p[i];
  sort(p.begin(), p.end());
  int ans = 0;
  p.back() /= 2;
  rep(i, n) {
    ans += p[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct Pos {
  int x, y;
};

int N;
Pos p[16];
vector<vector<int>> g;

int gcd(int x, int y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}

pair<int, int> grad(const Pos&a, const Pos& b) {
  int x = a.x - b.x;
  int y = a.y - b.y;
  int neg = x*y < 0 ? -1 : 1;
  int g = gcd(abs(x), abs(y));
  return make_pair((abs(x)/g), (abs(y)/g)*neg);
}

map<tuple<int, int, int, int>, int> cache;

int Solve(int i, int j, int c, int used) {
  if (i == g.size()) return 0;
  auto key = make_tuple(i, j, c, used);
  if (cache.count(key) > 0) return cache[key];
  if (j == g[i].size()) return Solve(i+1, 0, 0, used) + c * (c-1) / 2;
  int a = Solve(i, j+1, c, used);
  if ((used & g[i][j]) == 0) {
    a = max(a, Solve(i, j+1, c+1, used | g[i][j]));
  }
  return cache[key] = a;
}

int main() {
  while (cin >> N) {
    cache.clear();
    for (int i = 0; i < N; ++i) {
      cin >> p[i].x >> p[i].y;
    }
    map<pair<int, int>, vector<int>> cnt;
    for (int i = 0; i < N; ++i) {
      for (int j = i+1; j < N; ++j) {
	cnt[grad(p[i], p[j])].push_back((1<<i) | (1<<j));
      }
    }
    g.clear();
    for (const auto& kv : cnt) {
      auto& c = kv.second;
      if (c.size() > 1)
	g.push_back(c);
    }
    sort(g.begin(), g.end(), [](const auto& a, const auto& b){ return a.size() > b.size();});
    cout << Solve(0, 0, 0, 0) << endl;
  }
}

Measured memory_bytes: 27572
#import<atcoder/all>
int N,Q,i,a;main(){scanf("%d%d",&N,&Q);atcoder::fenwick_tree<long>b(N);for(;i++<N;b.add(i-1,a))scanf("%d",&a);for(;scanf("%d%d%d",&i,&a,&N),Q--;){if(i)printf("%ld\n",b.sum(a,N));else b.add(a,N);}}

Measured memory_bytes: 8224
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <numeric>

using namespace std;

#define int long long
typedef long double ld;
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<vi>
#define viii vector<vii>
#define vpii vector<pii>
#define vb vector<bool>
#define vbb vector<vb>
#define vs vector<string>
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define in(a, x) for (int i = x; i < (a).size(); ++i) cin >> (a)[i]
#define out(a) for (auto qwe : a) cout << qwe << " "

const int INF = 1e9;
const int INF64 = 1e18;
const int MOD = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int MOD3 = 998244353;
const int P = 37;

const int mxn = 200000;

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

    int n;
    cin >> n;

    string s;
    cin >> s;

    vii dp(n + 1, vi(n + 1, 0));
    vii p(n + 1, vi(n + 1, 0));

    dp[1][1] = 1;
    for (int k = 1; k <= n; ++k) {
        p[1][k] = 1;
    }

    for (int i = 2; i <= n; ++i) {
        bool less = s[i - 2] == '<';

        for (int j = 1; j <= i; ++j) {
            if (less) {
                dp[i][j] = p[i - 1][j - 1];
            } else {
                dp[i][j] = (p[i - 1][i - 1] - p[i - 1][j - 1] + MOD) % MOD;
            }

            p[i][j] = (p[i][j - 1] + dp[i][j]) % MOD;
        }
    }

    cout << p[n][n];
}

Measured memory_bytes: 141184
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

points = {'rr': 0, 'rs': R, 'rp': 0, 'sr': 0, 'ss': 0, 'sp': S, 'pr': P, 'ps': 0, 'pp': 0}
hands = ['r', 's', 'p']
ans = 0
for i in range(K):
    subT = T[i::K]
    n = len(subT)
    dp = [{h: 0 for h in hands} for _ in range(n)]
    for j, t in enumerate(subT):
        for hand in hands:
            dp[j][hand] = max(dp[j-1][h] for h in set(hands) - set([hand])) + points[hand + t]
    ans += max(dp[-1][h] for h in hands)
print(ans)

Measured memory_bytes: 42828
fun main(args: Array<String>) {
    val (a, b, c) = readLine()!!.split(" ").map { it.toInt() }
    if ((a == b && a != c) || (a == c && a != b) || (b == c && a != b)) {
        println("Yes")
    } else {
        println("No")
    }
}

Measured memory_bytes: 37812
from itertools import combinations
N = int(input())

def check(edge, s):
    nodes = [0] * (N+1)
    for a, b in edge:
        nodes[a] += b
        nodes[b] += a
    return all([s == i for i in nodes[1:]])

def main(N):
    # 合計になる2頂点のグループを作って、その塊でつないでいく
    group_sum = N if N % 2 == 1 else N+1
    edge = set()
    for i in range(1,N+1):
        for j in range(i+1, N+1):
            if i+j == group_sum: continue
            edge.add((i,j))
    print(len(edge))
    for e in edge:
        print(*e)

main(N)


Measured memory_bytes: 74356
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
from decimal import *
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines
input = sys.stdin.readline

A, V = map(int, input().split(" "))
B, W = map(int, input().split(" "))
T = int(input())

pdiff = abs(B-A)
vdiff = V-W
if vdiff > 0:
    if pdiff/vdiff <= T:
        print("YES")
        exit()
    print("NO")
else:
    print("NO")


Measured memory_bytes: 9888
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define ll long long
using namespace std;
int main() {
  ll N = 0;
  cin >> N;
  vector<ll>A(N);
  vector<ll>sum(N);
  sum[0] = 0;
  rep(i,N){
    cin >> A[i];
  }
  rep(i,N){
    sum[i+1] = sum[i] + A[i];
  }
  ll ansmin = 3000000000000000000;
  rep(i,N-1){
    ll x = 0,y = 0;
    x = sum[i+1];
    y = sum[N] - sum[i+1];
    ansmin = min(ansmin,abs(x-y));
  }
  cout << ansmin;
}
      

Measured memory_bytes: 6364
unittest
{
	assert( [ "2 3 1", "3 3", "3 3 3", "1 2 1" ].parse.expand.solve == 5 );
	assert( [ "1 1 2", "10", "10", "1 1 5", "1 1 10" ].parse.expand.solve == 10 );
	assert( [ "2 2 1", "3 5", "3 5", "2 2 2" ].parse.expand.solve == 6 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto abm = input.front.split.to!( long[] );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	input.popFront;
	auto bs = input.front.split.to!( long[] );
	auto xycs = new long[ 3 ][ abm[ 2 ] ];
	foreach( ref xyc; xycs )
	{
		input.popFront;
		xyc = input.front.split.to!( long[] );
		xyc[ 0 .. 2 ] -= 1;
	}
	return tuple( as, bs, xycs );
}

auto solve( long[] as, long[] bs, long[ 3 ][] xycs )
{
	auto ans = as.reduce!min + bs.reduce!min;
	foreach( xyc; xycs )
	{
		ans = min( ans, as[ xyc[ 0 ] ] + bs[ xyc[ 1 ] ] - xyc[ 2 ] );
	}
	return ans;
}


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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  while(a > 0 && c > 0) {
    c -= b;
    a -= d;
  }
  if(c <= 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3620
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const long long LINF = 1000000000000000018ll;
const int INF = 1000000009;
const int mod = 1000000007;
const int mod2 = 998244353;

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

vector<int> period;
vector<bool> visited;

void dfs(int cur_v, vector<int> &To) {
  if (visited[cur_v]) {
    period.push_back(cur_v + 1);
    return;
  } else {
    visited[cur_v] = true;
    period.push_back(cur_v + 1);
    int nxt_v = To[cur_v];
    dfs(nxt_v, To);
  }
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::setprecision(20) << std::fixed;

  long long N, K;
  cin >> N >> K;

  vector<int> To(N);
  for (int i = 0; i < N; i++) {
    int t;
    cin >> t;
    To[i] = t - 1;
  }

  visited = vector<bool>(N + 1, false);

  dfs(0, To);

  long long P = period.size() - 1;
  long long head, tail = P - 1;

  for (int i = 0; i < P; i++) {
    if (period[i] == period[P]) {
      head = i;
    }
  }
  if (K <= P) {
    cout << period[K] << endl;
  } else {
    K -= (head);
    K %= (tail - head + 1);
    cout << period[head + K] << endl;
  }
  return 0;
}

Measured memory_bytes: 14096
#include <iostream>
using namespace std;
int main(void){
    int N;
    cin>>N;
    
    int odd=0;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        if(a%2==1)odd++;
    }
    
    if(odd%2==1){
        cout<<"NO"<<endl;
    }else{
        cout<<"YES"<<endl;
    }
    
}


Measured memory_bytes: 256
n = input()
s = raw_input()

MOD = 10**9+7
dp = [1]
for i in xrange(n):
    dp2 = [0]*(i+2)
    for j in xrange(i+1):
        dp2[j+1] += dp[j]
        dp2[j+1] %= MOD
    for j in xrange(1, i+1):
        dp2[j-1] += 2*dp[j]
        dp2[j-1] %= MOD
    dp2[0] = (dp2[0] + dp[0]) % MOD
    dp = dp2
print dp2[len(s)]

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

int main(void)
{
    int N, K;
    int ans = 1000000000;
    cin >> N >> K;
    int x[N];
    for (int i = 0; i < N; i++)
    {
        cin >> x[i];
    }

    int tmp, r, l;
    for (int j = 0; j < N - K + 1; j++)
    {
        l = x[j];
        r = x[j + K - 1];
        tmp = min(abs(r) + abs(r - l), abs(l) + abs(r - l));
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    string num;
    while (1)
    {
        int i, ans = 0;
        cin >> num;
        if (num == "0")
            break;

        for (i = 0; i < num.length(); i++)
            ans += num[i] - '0';
        printf("%d\n", ans);
    }
}


Measured memory_bytes: 3180
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for(auto v:(V))cout<<v<<" "<<endl
inline int GCD(int a, int b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;

int main()
{
    string b;
    cin >> b;
    rep(i, b.size())
    {
        if (b.at(i) == 'A')
            cout << 'T';
        if (b.at(i) == 'T')
            cout << 'A';
        if (b.at(i) == 'C')
            cout << 'G';
        if (b.at(i) == 'G')
            cout << 'C';
    }
    cout << endl;
}

Measured memory_bytes: 256
//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*
        PEOPLE'S LIVES DON'T END WHEN THEY DIE.
        IT ENDS WHEN THEY LOSE FAITH
                                     -ITACHI UCHIHA
        EXPLAINATION BELOW->
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
ll gcd(ll a,ll b);
ll lcm(ll a,ll b);
ll modularExponentiation(ll x,ll n,ll M);
void dsp(vector<ll> &V);
void dsp2(vector<pair<ll,ll>>&V);
void dsp3(map<ll,ll>&M);
double fact(double n);
ll nPr(ll n,ll r);
ll nCr(ll n,ll r);
ll r[40001];
ll c[40001];
void solve()
{
   string s;cin>>s;
   ll a,b,i;
   a=b=0;
   for(i=0;i<sz(s);i++)
   {
       if(s[i]=='A')a++;
       else b++;
   }
   if(a==0||b==0)
       cout<<"No\n";
   else
       cout<<"Yes\n";
}
int main()
{
   fastio
    solve();
  return 0;
}
ll gcd(ll a,ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
          
} 
ll lcm(ll a,ll b)  
{  
    return (a*b)/gcd(a, b);  
}  
ll modularExponentiation(ll x,ll n,ll M)
{   
    ll result=1;
    while(n>0)
    {
        if(n % 2 ==1)
        result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
        return result;
}
void dsp(vector<ll> &V)
{
    ull j;
    for(j=0;j<V.size();j++)
    {
        cout<<V[j]<<" ";
    }
    cout<<endl;
}
void dsp2(vector<pair<ll,ll>>&V)
{
    ull j;
    for(j=0;j<V.size();j++)
    {
        cout<<V[j].first<<" "<<V[j].second<<" ";
    }
    cout<<endl;
}
void dsp3(map<ll,ll>&M)
{
      map<ll,ll>::iterator it=M.begin();
      while(it!=M.end())
      {
        cout<<it->first<<" "<<it->second<<endl;
        it++;
      }
}
double fact(double n)
{
    double i=1;
    double res=1;
    
    if(n==0)
        return 1.00;
    
    while(i<=n)
    {
        res*=i;
        i++;
    }
    
    return res;
}
ll nPr(ll n,ll r)
{
    return (fact(n)/fact(n-r));
}
ll nCr(ll n,ll r)
{
    return (fact(n)/(fact(r)*fact(n-r)));
}
//map<ll,ll,greater<int>> to sort in descending order ,in iterator declaration no greater<int>

Measured memory_bytes: 256
n = int(input())
s = 0
for i in range(1, n+1):
    s += i
    if s >= n:
        break

k = s-n
ans = []
for j in range(1, i+1):
    if j == k:
        continue
    else:
        ans.append(j)
ans = list(map(str, ans))
print('\n'.join(ans))


Measured memory_bytes: 39024
n = int(input())
s, ans, num = 1, 1, 2
for i in range(2, n+1):
  s *= i
l = []
while s != 1:
  if not s % num:
    l.append(num)
    s //= num
  else:
    num += 1
for i in set(l):
  ans *= l.count(i)+1
print(ans%(10**9+7))

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

const int mod = 1e9 + 7, N = 1e5 + 10;

ll pw(ll a, ll b) {
    ll r = 1;
    for( ; b ; b >>= 1, a = a * a % mod) {
        if(b & 1) {
            r = r * a % mod;
        }
    }
    return r;
}

ll getinv(ll n) {
    return pw(n, mod - 2);
}

void upd(ll &a, ll b) {
    a = (a + b) % mod;
}

int n;
ll fac[N], invfac[N];
vector<int> g[N];
void init(int n) {
    fac[0] = invfac[0] = 1;
    for(int i = 1 ; i <= n ; ++ i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    invfac[n] = pw(fac[n], mod - 2);
    for(int i = n - 1 ; i ; -- i) {
        invfac[i] = invfac[i + 1] * (i + 1) % mod;
    }
}

ll C(int n, int m) {
    return n < m || m < 0 ? 0 : fac[n] * invfac[n - m] % mod;
}

ll ans;
int k;
int main() {
    init(N - 1);
    scanf("%d%d", &n, &k);
    for(int i = 1, u, v ; i < n ; ++ i) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ans = k;
    for(int i = 1 ; i <= n ; ++ i) {
        int sz = g[i].size() - (i > 1);
        ans = ans * C(k - 1 - (i > 1), sz) % mod;
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 7672
#include<stdio.h>

int selectionsort(int a[],int n){
  int i,j;
  int minj;
  int esc;
  int count=0;
  for(i=0;i<n;i++){
    minj = i;
    for(j=i;j<n;j++){
      if(a[j]<a[minj]){
	minj = j;
      }
    }
    if(a[i]!=a[minj]){
      esc = a[i];
      a[i] = a[minj];
      a[minj] = esc;
      count++;
    }
  }
  return count;
}  


int main(void){
  int n;
  int a[100]={};
  int i;
  int count;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  count = selectionsort(a,n);
  for(i=0;i<n;i++){
    printf("%d",a[i]);
    if(i!=n-1) printf(" ");
  }
  printf("\n%d\n",count);
  return 0;
}

Measured memory_bytes: 1768
#include <iostream> 
#include <string> 
#include <vector> 
#include <cmath> 
#include <algorithm> 
#include <cstdlib> 
#include <ctime> 
#include <cstdio> 
#include <functional> 
#include <set> 
#include <queue> 
#include <cctype> 
#include <climits> 
#include <stack> 
#include <map> 
#include <cstring> 

using namespace std; 

const long long mod=1e9+7;

int main(){
    int a,b;
    cin>>a>>b;

    cout << 6-a-b << endl;


    return 0;
}

Measured memory_bytes: 256
#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;
bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b){return (a.second < b.second);}
ll gcd(ll a, ll b){if(a==0)return b;return gcd(b % a, a);}
int main()
{
	chutiyaap;
	string s;cin>>s;
	ll res=0;
	ll l=0,r=s.length()-1;
	while(r>l)
	{
		if(s[l]!=s[r])res++;
		r--;
		l++;
	}
	cout<<res;
}


Measured memory_bytes: 256
n = int(input())
R = []
for i in range(n):
    R.append(int(input()))

ans = R[1] - R[0]

M = R[-1]
for i in range(n-2,-1,-1):
    s = R[i]
    if M - s > ans:
        ans = M-s
    if M < s:
        M = s

print(ans)


Measured memory_bytes: 13588
import java.util.Scanner;
public class Main {
	private static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		
		SelectionSort(a);
		
		for(int i = 0; i < a.length; i++) {
			System.out.print(a[i]);
			if(i != a.length-1) {
				System.out.print(" ");
			}
		}
		System.out.println("\n" + count);
	}
	
	public static int[] SelectionSort(int[] a) {
		for(int i = 0; i < a.length; i++) {
			int minj = i;
			for(int j = i+1; j < a.length; j++) {
				if(a[j] < a[minj]) {
					minj = j;
				}
			}
			if(minj != i) {
				int tmp = a[i];
				a[i] = a[minj];
				a[minj] = tmp;
				count++;
			}
		}
		return a;
	}

}



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

int main () { 
    int N, min = 1e+9 + 1;
    int max_price = -(1e+9 + 1), tmp;
    cin >> N;
    int R[N];

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

    for (int i = 0; i < N; i++) {
        if (i != 0) {
            tmp = R[i] - min;
            if (tmp > max_price) {
                max_price = tmp;
            }
        }

        if (R[i] < min) {
            min = R[i];
        }
    }

    cout << max_price << endl;

    return 0;
}


Measured memory_bytes: 3896
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
t=0
x=0
y=0
flag=True
for i in range(n):
    tt=l[i][0]-t
    d=abs(l[i][1]-x)+abs(l[i][2]-y)
    if tt<d or tt%2!=d%2:
        flag=False
    t=l[i][0]
    x=l[i][1]
    y=l[i][2]
if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 60376
#include <stdio.h>
int main(void)
{
 int h,w,a,i;
  
  while(1){
  scanf("%d", &h);
  scanf("%d", &w); 
   if(h == 0 && w == 0) break;
    
    for(i =1; i<= h; i++){
     for(a = 1; a<= w; a++){
      printf("#");
     }
     printf("\n");
     }
      printf("\n");
  }
return 0;
}

Measured memory_bytes: 572
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextWord() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, e := strconv.Atoi(nextWord())
	if e != nil {
		panic(e)
	}
	return i
}

func max(v1, v2 int) int {
	if v1 > v2 {
		return v1
	}
	return v2
}

func main() {
	var dp [105][100005]int

	sc.Split(bufio.ScanWords)
	n := nextInt()
	ww := nextInt()
	var w, v []int
	for i := 0; i < n; i++ {
		w = append(w, nextInt())
		v = append(v, nextInt())
	}

	// i番目の品物
	for i := 0; i < n; i++ {
		for j := 0; j <= ww; j++ {
			if j >= w[i] {
				dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
			} else {
				dp[i+1][j] = dp[i][j]
			}
		}
	}

	ans := dp[n][ww]
	fmt.Println(ans)
}


Measured memory_bytes: 81920
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

int main()
{
    int n;
    cin>>n;
    vector<int> p(n);
    REP(i,n) cin>>p[i];

    int v=0;
    REP2(i,1,n-1){
        if(p[i-1]<=p[i] && p[i]<p[i+1]) v++;
        else if(p[i-1]>p[i] && p[i]>=p[i+1]) v++;
    }
    
    cout<<v<<endl;
    
	return 0; 
}

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

int main() {
    int X, Y, Z, K; cin >> X >> Y >> Z >> K;
    vector<ll> A(X), B(Y), C(Z);
    rep(i, X){
        cin >> A[i];
    }
    rep(i, Y){
        cin >> B[i];
    }
    rep(i, Z){
        cin >> C[i];
    }
    vector<ll> AB;
    rep(i, X){
        rep(j, Y){
            AB.push_back(A[i] + B[j]);
        }
    }
    sort(AB.begin(), AB.end(), greater<ll>());
    vector<ll> ans;
    int a = AB.size();
    a = min(a, K);
    rep(i, a){
        rep(j, Z){
            ans.push_back(AB[i] + C[j]);
        }
    }
    sort(ans.begin(), ans.end(), greater<ll>());
    rep(i, K){
        cout << ans[i] << endl;
    }



    return 0;
}

Measured memory_bytes: 43368
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e9+7;
int n,m,x;
struct zz{
	int a[4][4];
}Ans,f1,f2;
zz cf(zz x,zz y){
	zz z;memset(z.a,0,sizeof z.a);
	for (int i=0;i<4;i++)
		for (int j=0;j<4;j++)
			for (int k=0;k<4;k++)
				(z.a[i][j]+=x.a[i][k]*y.a[k][j])%=M;
	return z;
}
zz ksm(zz x,int y){
	zz Ans;
	memset(Ans.a,0,sizeof Ans.a);
	for (int i=0;i<4;i++)Ans.a[i][i]=1;
	for (;y;y>>=1,x=cf(x,x))
		if (y&1)Ans=cf(Ans,x);
	return Ans;
}
signed main(){
	for (int i=0;i<=4;i++)
		for (int j=0;j<=4;j++)
			if ((i&j)==j)f1.a[i][i^j]=f2.a[i][i^j]=1;
	for (int i=0;i<=3;i++)f1.a[i][3]+=1;
	scanf("%lld%lld",&n,&m);
	int last=0;
	for (int i=0;i<4;i++)Ans.a[i][i]=1;
	for (int i=1;i<=m;i++){
		scanf("%lld",&x);
		Ans=cf(Ans,ksm(f1,x-last-1));
		last=x;
		Ans=cf(Ans,f2);
	}
	Ans=cf(Ans,ksm(f1,n-last));
	printf("%lld\n",Ans.a[3][0]);
}


Measured memory_bytes: 256
// #include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
// #include <algorithm>
#define pb push_back
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// #define cerr if(0)cerr
using namespace std;
typedef long long LL;

const int N=100010;
const LL  I=1e18;
int n,k;
LL T[N],DP[N];

LL abso(LL x){
  if(x<0) return -x;
  return x;
}

LL mino(LL x, LL y){
  if(y<x)return y;
  return x;
}

LL f(int x)
{
  LL res=I;
  for(int i=max(1,x-k); i<x; i++)
  {
    res=mino(res,abso(T[x]-T[i])+DP[i]);
  }
  return res;
}

int main()
{
  // boost;
  scanf("%d%d",&n,&k);
  for(int i=1; i<=n; i++)
  {
    scanf("%lld",&T[i]);
  }
  for(int i=2; i<=n; i++)
  {
    DP[i]=f(i);
  }
  printf("%lld",DP[n]);

  return 0;
}


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

#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define li long long
#define ld long double
#define x first
#define y second
#define pt pair<int, int>
#define pll pair<li, li>
#define forn(i, t) for(int i = 0; i < (t); i++)
#define fore(i, f, t) for(int i = (f); i < (t); i++)
#define forr(i, f, t) for(int i = (f) - 1; i >= (t); i--)
#define all(x) (x).begin(), (x).end()
#define ins insert

using namespace std;


const int INF = 1e9;
const int MOD = 1e9 + 7;
const li INF64 = 1e18;
const ld EPS = 1e-7;

mt19937 myrand(time(NULL));

li n, a, b, c, d;


bool read(){
	if(scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d) != 5)
		return 0;
	b -= a;
	return 1;
}


void solve(){
	forn(i, n){
		li l1 = c * i, r1 = d * i;
		li l2 = (n - 1 - i) * c, r2 = (n - 1 - i) * d;
		if (l1 - r2 <= b && b <= r1 - l2){
			puts("YES");
			return;
		}
	}
	puts("NO");
}


int main(){
	#ifdef _DEBUG
		freopen("input.txt", "r", stdin);
	#endif
	while(read())
		solve();
	return 0;
}

Measured memory_bytes: 3748
s=list(str(input()))

if s[0]==s[1] and s[1]==s[2] and s[2]=='R':
    print(3)
elif s[1]==s[2] and s[2]=='R':
    print(2)
elif s[0]==s[1] and s[1]=='R':
    print(2)
elif s[1]=='R' or s[2]=='R' or s[0]=='R':
    print(1)
else:
    print(0)

Measured memory_bytes: 9064
#include"bits/stdc++.h"
#include <iostream>
#include <vector>


using namespace std;


int main(){
	
	int N,W;

	cin >> N >> W ;

	vector<vector<int> > dp(N+1, vector<int>(W+1));
	
	vector<int> v(N);
	vector<int> w(N);

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


	for(int i = N-1; i >= 0; i--){
		for(int j= 0; j <= W; j++){
			if(w[i] > j){
				dp[i][j] = dp[i+1][j];
			}

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

		}

	}

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

	return 0;
}


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

using namespace std;

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

    sort(A.begin(), A.end(),greater<int>());

    int Alice = 0;
    int Bob = 0;
    for(int i = 0; i < n; i++){
        if(i % 2 == 0) Alice += A[i];
        else Bob += A[i]; 
    }

    cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n, a[100001];
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  sort(a+1, a+n+1);
  int idx = lower_bound(a+1, a+n+1, a[n]/2)-a, x;
  if(abs(a[idx+1]*2-a[n]) > abs(a[idx]*2-a[n])) {
    if(abs(a[idx]*2-a[n]) > abs(a[idx-1]*2-a[n])) x = idx-1;
    else x = idx;
  }
  else {
    if(abs(a[idx+1]*2-a[n]) > abs(a[idx-1]*2-a[n])) x = idx-1;
    else x = idx+1;
  }
  printf("%d %d\n", a[n], a[x]);
}

Measured memory_bytes: 512
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 r = sc.nextInt();
		int c = sc.nextInt();
		int [][] cell = new int[r+1][c+1];

		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				cell[i][j] = sc.nextInt();
			}
		}
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				cell[i][c] += cell[i][j];
				cell[r][j] += cell[i][j];
				System.out.printf("%d ",cell[i][j]);
			}
			System.out.println(cell[i][c]);
			cell[r][c] += cell[i][c];
		}
		for(int i = 0; i < c; i++) {
			System.out.printf("%d ",cell[r][i]);
//			cell[r][c] += cell[r][i];
		}
		
		System.out.println(cell[r][c]);
		

	}
}



Measured memory_bytes: 61688
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans=a[0]
n-=2
for i in a[1:]:
  if n == 0:
    break
  if n == 1:
    ans += i
    break
  ans += i*2
  n -= 2
print(ans)
  

Measured memory_bytes: 31388
#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;

using ll=long long;

int main() {
  int N,K; cin>>N >>K;
  vector<bool> kirai(10);
  rep(i,0,K) {
    int D; cin >>D;
    kirai[D]=true;
  }
  while (true) {
    string check=to_string(N);
    bool flag=true;
    rep(i,0,10) {
      int result=check.find(to_string(i));
      if (kirai[i]==true && result!=-1) {
        flag=false;
        break;
      }
    }
    if (flag) break;
    N++;
  }
  cout <<N <<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
#define pri 1000000007
#define pr pair <ll,ll>

using namespace std;

void masterstroke(){
ll n,m;
cin>>n>>m;
set <ll> a[m];
for(ll i=0;i<m;i++){
	ll k;
	cin>>k;
	for(ll j=0;j<k;j++){
		ll y;
		cin>>y;
		a[i].insert(y);
		}
}	
ll p[m];
for(ll i=0;i<m;i++){
	cin>>p[i];
}

ll x=pow(2,n);
ll ansi=0;
for(ll i=0;i<x;i++){
	ll f=i;
	ll ans[m]={0};
	ll za=1;
	while(f){
	ll s=f%2;
	if(s==1){
     for(ll x=0;x<m;x++){
     	if(a[x].find(za)!=a[x].end())ans[x]++;
     }

	}

	f=f/2;
	za++;
	}
	ll un=0;
   for(ll i=0;i<m;i++){
   	if(ans[i]%2!=p[i]){un=1;}
   }
   if(un==0)ansi++;

}
cout<<ansi<<endl;



	
}

int main() {
    ll t=1;
    //cin>>t;
    for(ll i=0;i<t;i++)masterstroke();
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
let _ =
  let n = Scanf.scanf "%d\n" (fun n -> n) in
  let h_max = ref 0 in
  let res = ref 0 in
  for i = 0 to n - 1 do
    let h = 
      Scanf.scanf (if i <> n - 1 then "%d " else "%d\n") (fun h -> h) in
    if h >= !h_max then (res := !res + 1; h_max := h);
  done;
  Printf.printf "%d\n" !res


Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(void){

int N,M,C;

cin >> N >> M >> C;

int B[M];
int A[N][M];

for (int m=0;m<M;m=m+1) {
cin >> B[m];
}


for (int n=0;n<N;n=n+1) {
for (int m=0;m<M;m=m+1) {
cin >> A[n][m]; 
}
}



int sum=0;//longではなくintではだめなのか試してみる
int count =0;

for (int n=0;n<N;n=n+1) {
sum=0;
for (int m=0;m<M;m=m+1) {
sum = sum + A[n][m]*B[m];
}

if (sum+C>0) count = count +1;
}

cout << count << endl ;

}


Measured memory_bytes: 256
N = gets.to_i
P = gets.split.map(&:to_i)

cnt = 0
min = 999999999
(0..(N-1)).each do |i|
  if P[i] <= min
    min = P[i]
  end
  if !(P[i] > min)
    cnt += 1
  end
end

puts cnt

Measured memory_bytes: 15236
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

int x[20][20], y[20][20];
int a[20];

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


    rep(i, n){
        int p; cin >> p;
        a[i] = p;
        rep(j, p) {
            int c, d;
            cin >> c >> d;
            c--;
            x[i][j] = c;
            y[i][j] = d;
        }
    }

    int ans = 0;

    for(int bits = 0; bits < (1<<n); bits++){
        bool flag = 1;
        rep(i, n){
            if (!(bits&(1<<i))) continue;
            rep(j, a[i]){
                if ((1 & (bits>>x[i][j])) ^ y[i][j]) flag = 0;
            }
        }
        if (flag) ans = max(ans, __builtin_popcount(bits));
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3532
using System;

public class ITP1_6_C
{
  static void Main()
  {
    int[,,] house = new int[4, 3, 10];
    for (int i = 0; i < 4; i++)
    {
      for (int j = 0; j < 3; j++)
      {
        for (int k = 0; k < 10; k++)
        {
          house[i, j, k] = 0;
        }
      }
    }

    int c = int.Parse(Console.ReadLine());
    int b, f, r, v;

    for (int i = 0; i < c; i++)
    {
      string[] data = Console.ReadLine().Split(' ');
      b = int.Parse(data[0]);
      f = int.Parse(data[1]);
      r = int.Parse(data[2]);
      v = int.Parse(data[3]);
      house[b - 1, f - 1, r - 1] += v;
    }

    for (int i = 0; i < 4; i++)
    {
      for (int j = 0; j < 3; j++)
      {
        for (int k = 0; k < 10; k++)
        {
          Console.Write(" {0}", house[i, j, k]);
        }
        Console.Write("\n");
      }
      if (i != 3) Console.WriteLine("####################");
    }
  }
}

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

int main() {
  int n,k;
  cin>>n>>k;
  int sum;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    sum+=min(2*x,2*abs(x-k));
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;
#define ll long long
int n,m;

int a[100010];
int main()
{
    scanf("%d",&n);
    int cnt = 0,x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        for(int j=x;j<=y;j++)
        {
            if(a[j] == 0)
            {
                a[j] = 1;
                cnt++;
            }
        }

    }
    cout<<cnt<<endl;
    return 0;
}


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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO  cout << "NO"  << endl
#define No  cout << "No"  << endl

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;

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

void solve()
{
    int N; cin >> N;
    vi A(N); REP(i, N) cin >> A[i];
    sort(ALL(A));
    int ans = A[0];
    REP(i, N) 
    {
        ans = gcd(ans, A[i]);
    }
    cout << ans << endl;
}
    
int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
// constexpr ll MOD = 998244353;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

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

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

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

int main(void) {
    int N;
    cin >> N;
    vector<ll> A(300010);
    for (int i=0;i<N;i++) cin >> A[i];

    ll res = 0;
    for (int j=0;j<60;j++) {
        ll zero = 0, one = 0;
        const ll X = (1LL << j);
        for (int i=0;i<N;i++) {
            if (A[i] & X) one++;
            else zero++;
        }
        // cout << (zero*one % MOD) * (X%MOD) << endl;
        res += ((zero*one % MOD) * (X%MOD)) % MOD;
        res %= MOD;
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0first3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

int sx,sy,tx,ty;

int main() {
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    for (int i=sx;i<tx;i++) {
        putchar('R');
    }
    for (int i=sy;i<ty;i++) {
        putchar('U');
    }
    for (int i=sx;i<tx;i++) {
        putchar('L');
    }
    for (int i=sy;i<ty;i++) {
        putchar('D');
    }
    putchar('D');
    for (int i=sx;i<=tx;i++) {
        putchar('R');
    }
    for (int i=sy;i<=ty;i++) {
        putchar('U');
    }
    putchar('L');
    putchar('U');
    for (int i=sx;i<=tx;i++) {
        putchar('L');
    }
    for (int i=sy;i<=ty;i++) {
        putchar('D');
    }
    putchar('R');
    printf("\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define Keep_calmYou_are_still_learning ios_base::sync_with_stdio(false);cin.tie(NULL);//freopen("out.txt","w",stdout);
typedef long long ll;
typedef long double ld;
using namespace std;


int main()
{
    Keep_calmYou_are_still_learning;


    ll k , n,ans=INT_MAX;
    cin>>n>>k;
    ll h[n+1];
    for (ll i=0;i<n;i++)
        cin>>h[i];
    sort(h,h+n);
    for (ll i=k-1;i<n;i++)
        ans=min(ans,h[i]-h[i+1-k]);
    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <vector>
#include <set>
#include <map>
using namespace std;
long long solve(const vector<pair<pair<int,int>,pair<int,int>>> &v){
	set<int>lx,ly;
	for(auto &e:v){
		lx.insert(e.first.first);lx.insert(e.second.first);
		ly.insert(e.first.second);ly.insert(e.second.second);
	}
	int i;
	map<int,int>mx,my,sx,sy;
	i=0;for(auto ix1=lx.begin(),ix2=lx.begin();++ix2!=lx.end();++ix1,++i){
		mx[*ix1]=i,sx[i]=*ix2-*ix1;
	}
	mx[*lx.rbegin()]=i,sx[i]=0;
	i=0;for(auto iy1=ly.begin(),iy2=ly.begin();++iy2!=ly.end();++iy1,++i){
		my[*iy1]=i,sy[i]=*iy2-*iy1;
	}
	my[*ly.rbegin()]=i,sy[i]=0;
	vector<vector<int>>m(my.size());
	for(auto &e:m)e.resize(mx.size());
#if 0
	for(auto &e:v){
		for(int y=my[e.first.second];y<my[e.second.second];y++)
			for(int x=mx[e.first.first];x<mx[e.second.first];x++)m[y][x]++;
	}
#else
	for(auto &e:v){
		m[my[e.first.second]][mx[e.first.first]]++;
		m[my[e.second.second]][mx[e.first.first]]--;
		m[my[e.first.second]][mx[e.second.first]]--;
		m[my[e.second.second]][mx[e.second.first]]++;
	}
	for(int y=0;y<sy.size();y++)for(int x=1;x<sx.size();x++)m[y][x]+=m[y][x-1];
	for(int y=1;y<sy.size();y++)for(int x=0;x<sx.size();x++)m[y][x]+=m[y-1][x];
#endif
	int r=0;
	for(int y=0;y<sy.size();y++)for(int x=0;x<sx.size();x++)r=max(r,m[y][x]);
	return r;
}
int main(){
	int N,x1,y1,x2,y2;
	vector<pair<pair<int,int>,pair<int,int>>>v;
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		v.push_back({{x1,y1},{x2,y2}});
	}
	printf("%lld\n",solve(v));
}

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

n, w = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

V_MAX = 10**5
dp = [[w + 1] * (V_MAX + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i, (wi, vi) in enumerate(items):
    for j in range(V_MAX + 1):
        if j >= vi:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - vi] + wi)
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for i in range(n + 1):
    for j in range(V_MAX + 1):
        if dp[i][j] <= w:
            ans = max(ans, j)

print(ans)


Measured memory_bytes: 147240
#include <iostream>
#include <iomanip>

using namespace std;

const int maxn = 3e2 + 10;

long double dp[maxn][maxn][maxn];
long double n;
int a[4];
long double ii , jj ,kk , zz;

int main() {
    
    cin >> n;
    cout << setprecision(10) << fixed;
    for (int i = 0; i < n; i++) {
        int x;
        cin >>x;
        a[x]++;
    }
    for (int k = 0; k <= 302; k++) {
        for (int j = 0; j <= 302; j++) {
            for (int i = 0; i <= 302; i++) {
                if (i == 0 && j == 0&& k ==0)
                    continue;
                ii = 0;
                jj = 0;
                kk = 0;
                if (k != 0)
                    kk = (k / (long double)(i + j + k)) * (dp[i][j + 1][k - 1]);
                if (j != 0)
                    jj = (j / (long double)(i + j + k)) * (dp[i+1][j-1][k]);
                if (i != 0)
                    ii = (i / (long double)(i + j + k)) * (dp[i-1][j][k]);
                dp[i][j][k] += ii + jj + kk + 1 + ((n-(i + j + k)) / (long double)(i+j+k));
            }
        }
    }
    cout << dp[a[1]][a[2]][a[3]] << endl;
    return 0;
}

Measured memory_bytes: 456960
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll n, m, q;
    cin >> n >> m >> q;
    vector<vector<ll>> sums(200010, vector<ll>(510, 0));
    for (ll i = 0; i < m; i++)
    {
        ll l, r;
        cin >> l >> r;
        sums[l][r]++;
    }
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            sums[i + 1][j + 1] += sums[i + 1][j];
        }
    }
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            sums[i + 1][j + 1] += sums[i][j + 1];
        }
    }
    for (ll i = 0; i < q; i++)
    {
        ll l, r;
        cin >> l >> r;
        cout << sums[r][r] + sums[l - 1][l - 1] - sums[l - 1][r] - sums[r][l - 1] << endl;
    }
}

Measured memory_bytes: 805632
# C - 3 Steps
import sys
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
graph = [[] for _ in range(N)]

for a, b in AB:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

# 二部グラフかどうかの判定
colors = [None] * N
colors[0] = 0
q = [0]
while q:
    x = q.pop()
    for y in graph[x]:
        if colors[y] is None:
            colors[y] = 1 - colors[x]
            q.append(y)

# 二部グラフかどうか
is_bg = all(colors[a-1] != colors[b-1] for a, b in AB)

if is_bg:
    # 完全二部グラフにする
    x = sum(colors)
    y = N - x
    answer = x*y - M
else:
    # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)
    answer = N*(N-1)//2 - M

print(answer)

Measured memory_bytes: 42124
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fast() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")

int main()
{
	int N, M;
	cin >> N >> M;
	priority_queue<ll, vector<ll>, greater<ll>> pq;
	vector<pair<ll, ll>> ope;
	for (int i = 0; i < N; i++)
	{
		ll a;
		cin >> a;
		pq.push(a);
	}

	for (int i = 0; i < M; i++)
	{
		ll b, c;
		cin >> b >> c;
		ope.emplace_back(b, c);
	}

	sort(ope.rbegin(), ope.rend());

	for (int i = 0; i < M; i++)
	{
		int b = ope[i].first, c = ope[i].second;

		while (pq.top() < c && b > 0)
		{
			pq.pop();
			pq.push(c);
			b--;
		}
	}

	ll ans = 0;

	while (!pq.empty())
	{
		ans += pq.top();
		pq.pop();
	}

	cout << ans << "\n";
}

Measured memory_bytes: 3188