akhauriyash/Code-Regression huggingface dataset:
import java.util

import scala.io.StdIn
import scala.util.Try

object Main extends App {
  val INF: Long = 1e15.toLong
  val (n, x, y) = {
    val in = StdIn.readLine().split(" ").map(_.toInt)
    (in(0), in(1), in(2))
  }
  val sweets = for (_ <- 0 until n) yield {
    val k = StdIn.readLine().toInt
    for (_ <- 0 until k) yield {
      val in = StdIn.readLine().split(" ").map(_.toInt)
      Sweet(in(0), in(1), in(2))
    }
  }

  val dist = for (_ <- 0 until n) yield StdIn.readLine().split(" ").map(_.toLong)
  for (k <- 0 until n) for (i <- 0 until n) for (j <- 0 until n) dist(i)(j) = math.min(dist(i)(j), dist(i)(k) + dist(k)(j))

  val cost = Array.fill[Long](1 << n, n)(INF)
  cost(0)(0) = 0
  for (mask <- 0 until 1 << n)
    for (cur <- 0 until n)
      for (next <- 0 until n)
        if ((mask & (1 << next)) == 0) {
          val add = dist(cur)(next)
          cost(mask | (1 << next))(next) = math.min(cost(mask | (1 << next))(next), cost(mask)(cur) + add)
        }


  def knapsack(dp: Array[Long], available: Seq[Sweet]): Unit = {
    for {
      sweet <- available
      money <- 0 until sweet.price
    } {
      val deque = new util.ArrayDeque[(Int, Long)]()
      var num = 0
      while (num * sweet.price + money <= y) {
        val next = num * sweet.price + money


        val v = dp(next) - num * sweet.value
        while (!deque.isEmpty && deque.peekLast()._2 <= v) deque.pollLast()
        deque.addLast((num, v))

        dp(next) = deque.peekFirst()._2 + num * sweet.value
        if (deque.peekFirst()._1 == num - sweet.remain) deque.pollFirst()

        num += 1
      }
    }
    for (i <- 1 until dp.length) dp(i) = math.max(dp(i), dp(i - 1))
  }


  val prefix = n / 2
  val suffix = n - prefix

  val prefixDp = Array.fill[Long](1 << prefix, y + 1)(0)
  for (prefixMask <- 0 until 1 << prefix) {
    val mask = prefixMask << suffix
    val dp = prefixDp(prefixMask)
    val available = for {
      i <- 0 until n
      if (mask & (1 << i)) != 0
      sweet <- sweets(i)
    } yield sweet
    knapsack(dp, available)
  }

  val suffixDp = Array.fill[Long](1 << suffix, y + 1)(0)
  for (mask <- 0 until 1 << suffix) {
    val dp = suffixDp(mask)
    val available = for {
      i <- 0 until n
      if (mask & (1 << i)) != 0
      sweet <- sweets(i)
    } yield sweet
    knapsack(dp, available)
  }
  var ans = 0L
  for (mask <- 0 until 1 << n) {
    val suffixMask = mask & ((1 << suffix) - 1)
    val prefixMask = mask >> suffix
    val travelingCost = (for (last <- 0 until n) yield {
      cost(mask)(last) + dist(last)(0)
    }).min
    val money = math.min(x - travelingCost, y).toInt
    for (prefixMoney <- 0 to money) {
      val suffixMoney = money - prefixMoney
      val value = prefixDp(prefixMask)(prefixMoney) + suffixDp(suffixMask)(suffixMoney)
      ans = math.max(ans, value)
    }
  }
  println(ans)

  Try {

  }.recover {
    case e: Throwable => println(e)
  }

}

case class Sweet(price: Int, value: Int, remain: Int)

Measured memory_bytes: 575112
n=int(input())
aa=list(map(int,input().split()))
bb=list(map(int,input().split()))
cc=list(map(int,input().split()))
s = sum(bb[a-1] for a in aa)
for i in range(n-1):
    if aa[i]+1 == aa[i+1]:
        s += cc[aa[i]-1] 
print(s)

Measured memory_bytes: 3060
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <utility>

using std::pair;
typedef pair<int,int> pii;
const int N = 100010;
const int M = 11;
int _w;

int n, m, q, v[N], d[N], c[N], ans[N];

namespace G {
	int head[N], nxt[N*2], to[N*2], eid;
	void init() {
		eid = 0;
		memset(head, -1, sizeof head);
	}
	void link( int u, int v ) {
		to[eid] = v, nxt[eid] = head[u], head[u] = eid++;
		to[eid] = u, nxt[eid] = head[v], head[v] = eid++;
	}
}

int vis[N][M];
pii que[N*M];
int begin, end;

bool check( int u, int d ) {
	for( int i = d; i < M; ++i )
		if( vis[u][i] ) return true;
	return false;
}

void solve( int s, int d, int c ) {
	using namespace G;
	if( check(s, d) ) return;
	begin = end = 0, que[end++] = pii(s, d), vis[s][d] = 1;
	while( begin != end ) {
		pii o = que[begin++];
		int u = o.first, d = o.second-1;
		if( !ans[u] ) ans[u] = c;
		if( d == -1 ) continue;
		for( int i = head[u]; ~i; i = nxt[i] ) {
			int v = to[i];
			if( check(v, d) ) continue;
			vis[v][d] = 1, que[end++] = pii(v, d);
		}
	}
}

int main() {
	_w = scanf( "%d%d", &n, &m );
	G::init();
	for( int i = 0; i < m; ++i ) {
		int u, v;
		_w = scanf( "%d%d", &u, &v );
		G::link(u, v);
	}
	_w = scanf( "%d", &q );
	for( int i = 1; i <= q; ++i )
		_w = scanf( "%d%d%d", v+i, d+i, c+i );
	for( int i = q; i >= 1; --i )
		solve( v[i], d[i], c[i] );
	for( int i = 1; i <= n; ++i )
		printf( "%d\n", ans[i] );
	return 0;
}


Measured memory_bytes: 9600
price = int(input())

coin_500 = price // 500
price -= 500 * coin_500
coin_5 = price // 5

price -= 5 * coin_5
coin_100 = price // 100
price -= 100 * coin_100
coin_50 = price // 50
price -= 50 * coin_50
coin_10 = price // 10
price -= 10 * coin_10
coin_1 = price

print(1000 * coin_500 + coin_5 * 5)


Measured memory_bytes: 2940
#include<stdio.h>
int main(void){
    int en=0;
    long K,A,B,bis=1;
    scanf("%ld %ld %ld",&K,&A,&B);

    for(int i=0;i<K;i++){
        if(en==1){
            en--;
            bis+=B;
        }else if((bis>=A)&&(B>A+1)&&(i!=K-1)){
            bis-=A;
            en++;
        }else{
            bis++;
        }
        //printf("%d",bis);
    }
    printf("%ld",bis);
    return 0;
}

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


int main(void){

	int a[11],i,j;

	for (int i=1; i<11; i++){
		while (true){ 
		//cout << "山の高さ" << i << "（整数）" ;			
		cin >> a[i];
		if ((cin.good() == 1) && (a[i] >= 0) && (a[i] <= 10000)) {
			break;
		}
		}	
	}


	for (i=1; i<11; ++i){
		for (j=i+1; j<11 ; ++j){
		if (a[i] < a[j]){swap(a[i],a[j]);}
	}
			}


	for (i=1;i<4;++i){
		cout << a[i] << endl;
	}
		

		return 0;
	}

Measured memory_bytes: 1160
using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var str = Console.ReadLine();
        var strs = new List<string> { str.Substring(0, 1), str.Substring(1, 1), str.Substring(2, 1) };
        var result = strs.Contains("a") && strs.Contains("b") && strs.Contains("c") ? "Yes" : "No";
        Console.WriteLine(result);
    }
}

Measured memory_bytes: 13140
#include <stdio.h>
int main(void){
int a,b,c=0;
  scanf("%d %d",&a,&b);
  if(a>=b){c=c+a;a--;}
  else{c=c+b;b--;}
    if(a>=b){c=c+a;a--;}
  else{c=c+b;b--;}
  printf("%d",c);
return 0;
}

Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        // Here your code !
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        
        String[] tmpArray = line.split(" ");
        
        int overLimit = Integer.parseInt(tmpArray[0]);
        int prevDay = Integer.parseInt(tmpArray[1]);
        int overDay = Integer.parseInt(tmpArray[2]);
        
        if(prevDay >= overDay){
            System.out.println("delicious");
        }
        else if(prevDay + overLimit < overDay){
            System.out.println("dangerous");
        }
        else {
            System.out.println("safe");
        }
    }
}


Measured memory_bytes: 23380
import java.io.*;
import java.util.*;
import java.lang.*;
import java.awt.*;
import java.awt.geom.*;
import java.math.*;
import java.text.*;
import java.math.BigInteger.*;
import java.util.Arrays; 

public class   Main
{
  BufferedReader in;
  StringTokenizer as;
  int nums[],nums2[];
  int[] nums1[];
  boolean con = true;
  
  ArrayList < Integer >  ar = new ArrayList < Integer >();
  ArrayList < Integer >  fi = new ArrayList < Integer >();
  Map<Integer,Integer > map = new HashMap<Integer, Integer>();
  public static void main (String[] args)
  {
    new Main  ();
  }
  
  public int GCD(int a, int b) {
    if (b==0) return a;
    return GCD(b,a%b);
  }
  
  public int LIS(int arr[])
  {
    int n = arr.length;
    int sun[] = new int [n];
    int cur = 0;
    for(int x = 0;x<n;x++)
    {
      int temp = Arrays.binarySearch(sun,0,cur,arr[x]);
      if(temp < 0)
        temp = -temp -1;
      sun[temp] = arr[x];
      if(temp == cur)
        cur++;
    }
    return cur;
    
  }
  
  
  
  
  public Main  ()
  {
    try
    {
      
      in = new BufferedReader (new InputStreamReader (System.in));
      int a = nextInt();
      System.out.println((int)Math.pow(a,3));
      
    }
    catch(IOException e)
    {
      
    }
  }
  
  
  
  
  
  
  
  String next () throws IOException
  {
    while (as == null || !as.hasMoreTokens ())
    {
      as = new StringTokenizer (in.readLine ().trim ());
    }
    
    
    return as.nextToken ();
  }
  
  
  
  long nextLong () throws IOException
  {
    return Long.parseLong (next ());
  }
  
  
  int nextInt () throws IOException
  {
    return Integer.parseInt (next ());
  }
  
  
  double nextDouble () throws IOException
  {
    return Double.parseDouble (next ());
  }
  
  
  String nextLine () throws IOException
  {
    return in.readLine ().trim ();
  }
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

struct UnionFind{
  vector<int> v;
  UnionFind(int n) : v(n, -1) {}
  void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }
  int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (-v[x] < -v[y]) swap(x, y);
    v[x] += v[y]; v[y] = x;
    return true;
  }
  bool root(int x) { return v[x] < 0; }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -v[find(x)]; }
};

struct edge{
  int u,v,w;
};
bool operator<(const edge& a,const edge& b){
  return a.w < b.w;
}

int main(){
  int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  vector<edge> es;
  int tot=0;
  rep(i,m){
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    es.push_back((edge){a,b,c});
  }
  sort(all(es));
  vector<int> used;
  rep(i,m){
    if(uf.same(es[i].u,es[i].v))continue;
    uf.unite(es[i].u,es[i].v);
    tot+=es[i].w;
    used.push_back(i);
  }
  int resa=0,resb=0;
  rep(k,used.size()){
    uf.init();
    int sum=0;
    rep(i,m){
      if(uf.same(es[i].u,es[i].v)||i==used[k])continue;
      uf.unite(es[i].u,es[i].v);
      sum+=es[i].w;
    }
    if(tot<sum||uf.size(0)<n){
      resa++;
      resb+=es[used[k]].w;
    }
  }
  cout<<resa<<" "<<resb<<endl;
  return 0;
}



Measured memory_bytes: 3892
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define SZ(v) (int((v).size()))
#define ALL(vec) (vec).begin(),(vec).end()
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
using namespace std;
 
template<typename T, typename V = __gnu_pbds::null_type>
using ordered_set = __gnu_pbds::tree<T, V, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; // find_by_order(), order_of_key()

using ll = long long int;
using i64 = long long int;
template <typename T> inline bool uax(T &x, T y) {return (y > x) ? x = y, true : false;}
template <typename T> inline bool uin(T &x, T y) {return (y < x) ? x = y, true : false;}

void err(__attribute__((unused)) istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << a << endl;
  err(++it, args...);
}
template <typename T1, typename T2>
inline ostream& operator << (ostream& os, const pair<T1, T2>& buf) {
  return os << "(" << buf.first << ": " << buf.second << ")";
}
template<typename T>
inline ostream &operator << (ostream & os,const vector<T>& v) {
  bool first = true;
  os << "[";
  for(unsigned int i = 0; i < v.size(); i++) {
    if(!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template<typename T>
inline ostream &operator << (ostream & os,const set<T>& v) {
  bool first = true;
  os << "{";
  for (auto ii = v.begin(); ii != v.end(); ++ii) {
    if(!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "}";
}
inline ostream &operator << (ostream & os,const multiset<int>& v) {
  bool first = true;
  os << "{";
  for (auto x: v) {
    if(!first) os << ", ";
    os << x;
    first = false;
  }
  return os << "}";
}
template<typename T1, typename T2>
inline ostream &operator << (ostream & os,const map<T1, T2>& v) {
  bool first = true;
  os << "{";
  for (typename map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
    if(!first) os << ", ";
    os << *ii ;
    first = false;
  }
  return os << "}";
}
template<typename T>
ostream &operator << (ostream & os,const vector<vector<T>>& v) {
  for (auto &u: v) os << '\n' << u;
  return os;
}
template<typename T>
void finish(T ans) {cout << ans << '\n'; exit(0);}
const int MOD = 1e9 + 7;
const long long INF = 1e18;
const double EPS = 1e-6;
#define PI 3.14159265358979323846
/***********************************************************************/

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

  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int x = c * b + a * d - c * d;
  cout << a * b - x << '\n';
  
  return 0;
}


Measured memory_bytes: 256
s = input()
l = [0 for i in range(len(s)+1)]
if s[0] == '<':
  cnt = 1
  for i in range(0, len(s)):
    if s[i] == '<':
      l[i+1] = max(cnt, l[i+1])
      cnt += 1
    else:
      break
if s[-1] == '>':
  cnt = 1
  for i in range(len(s)-1, -1, -1):
    if s[i] == '>':
      l[i] = max(cnt, l[i])
      cnt += 1
    else:
      break
for i in range(1, len(s)):
  if s[i-1:i+1] == '><':
    #左側検索
    cnt = 1
    for j in range(i-1, -1, -1):
      if s[j] == '>':
        l[j] = max(cnt, l[j])
        cnt += 1
      else:
        break
    #右側検索
    cnt = 1
    for j in range(i, len(s)):
      if s[j] == '<':
        l[j+1] = max(cnt, l[j+1])
        cnt += 1
      else:
        break
ans = sum(l)
print(ans)

Measured memory_bytes: 77388
N, M = map(int, input().split())

cnt = [[0, 0] for _ in range(N)]

res = [0, 0]
for i in range(M):
    p, s = input().split()
    p = int(p) - 1

    if cnt[p][0] > 0:
        continue

    if s == "AC":
        cnt[p][0] += 1
        res[0] += 1
        res[1] += cnt[p][1]
    elif s == "WA":
        cnt[p][1] += 1

print(res[0], res[1])


Measured memory_bytes: 13172
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int n = saori.saori_hayami();
		int ans = 0;
		int num1 = 0;
		int num2 = 0;
		for(int i = 0;i < n;i++){
			num1 = saori.saori_hayami();
			num2 = saori.saori_hayami();
			ans += num2 - num1 + 1;
		}
		System.out.println(ans);

		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 21588
#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int>weight(N);
    for (int i = 0; i < N; i++) cin >> weight[i];

    vector<int>cul_sum(N+1, 0);
    for (int i = 0; i < N; i++) cul_sum[i+1] = (cul_sum[i] + weight[i]);

    int min_abs = 10000000; //
    for(int j = 1;j < N; j++){
        int tmp = abs(cul_sum[N] - 2 * cul_sum[j]);

        if (tmp <= min_abs) min_abs = tmp;
    }

    cout << min_abs << endl;
    return 0;
}


Measured memory_bytes: 256
/*
	0084:Search Engine
*/
#include	<iostream>
#include	<string>

using namespace std;

bool IsBreakChar(char c);

int main(void) {
	string str;
	bool IsFirst = true;
	
	getline(cin, str);
	
	int strln = (int)str.length();
	string word;
	for(int i = 0; i < strln; i++) {
		/*str[i]の文字列は区切り文字か？*/
		if( IsBreakChar(str[i]) ) {
			int wordln = (int)word.length();
			/*wordの文字列の長さは条件に合っているか？*/
			if(wordln >= 3 && wordln <= 6) {
				/*出力するのは初めてではないか？*/
				if(IsFirst == false) { cout << ' '; }
				cout << word;
				IsFirst = false;
			}
			word.clear();
		} else {
			word += str[i];
		}
	}
	cout << endl;
	
	return 0;
}

bool IsBreakChar(char c) {
	char brch[3] = { ' ', ',', '.' };
	
	for(int i = 0; i < 3; i++) {
		if(brch[i] == c) { return true; }
	}
	return false;
}

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

using namespace std;

class Point
{
	int r;
	int s;
	int p;

public:
	Point(int R, int S, int P) : r(R), s(S), p(P) {}
	int of(char c)
	{
		switch (c)
		{
		case 'r':
			return p;

		case 's':
			return r;

		case 'p':
			return s;

		default:
			return 0;
		}
	}
};

int main()
{
	int N, K, R, S, P;
	cin >> N >> K >> R >> S >> P;
	Point point(R, S, P);

	char c[200000];
	cin >> c;

	int ans = 0;

	for (int i = 0; i < N; i++)
	{
		if (c[i] != 'X')
		{
			ans += point.of(c[i]);

			if (c[i + K] != NULL && c[i + K] == c[i])
			{
				c[i + K] = 'X';
			}
		}
	}

	cout << ans;
}

Measured memory_bytes: 384
///
// File:  d.go
// Author: ymiyamoto
//
// Created on Tue May 15 23:23:20 2018
//
package main

import (
	"fmt"
)

type tree []int

func root(v int) int {
	if seg_tree[v] == v {
		return v
	} else {
		seg_tree[v] = root(seg_tree[v])
		return seg_tree[v]
	}
}

func unite(v, w int) {
	x := root(v)
	y := root(w)
	if x == y {
		return
	}
	seg_tree[x] = y
}

type set map[int]struct{}

func (s set) intersection(s1 set) set {
	s2 := set{}

	for k, _ := range s {
		if _, ok := s1[k]; ok {
			s2[k] = struct{}{}
		}
	}

	return s2
}

var N, M int
var p []int
var seg_tree tree
var rank tree

func main() {
	fmt.Scan(&N, &M)

	p = make([]int, N+1)
	for i := 1; i < len(p); i++ {
		fmt.Scan(&p[i])
	}

	seg_tree = make(tree, N+1)
	rank = make(tree, N+1)
	for i := 1; i < len(seg_tree); i++ {
		seg_tree[i] = i
		rank[i] = 0
	}

	for i := 0; i < M; i++ {
		var x, y int
		fmt.Scan(&x, &y)
		unite(x, y)
	}

	m := map[int]set{}
	m2 := map[int]set{}
	for i := 1; i < len(seg_tree); i++ {
		n := root(seg_tree[i])
		if _, ok := m[n]; !ok {
			m[n] = set{}
			m2[n] = set{}
		}
		m[n][i] = struct{}{}
		m2[n][p[i]] = struct{}{}
	}

	count := 0
	for k, v := range m {
		count += len(v.intersection(m2[k]))
	}
	fmt.Println(count)
}


Measured memory_bytes: 48768
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
string s;
int main() {
    DAU
    cin >> s;
    sort(s.begin(), s.end());
    if (s[0] == s[1] && s[2] == s[3] && s[1] != s[2])
        cout << "Yes";
    else cout << "No";
    PLEC
}


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

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        c: [chars; 3]
    }

    for (i, row) in c.iter().enumerate() {
        for (j, chr) in row.iter().enumerate() {
            if i == j {
                print!("{}", chr)
            }
        }
    }
}



Measured memory_bytes: 4352
#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
	int n, m, X, Y; scanf("%d %d %d %d", &n, &m, &X, &Y);
	int x[101], y[101];
	for(int i = 0; i < n; i++) scanf("%d", &x[i]);
	for(int i = 0; i < m; i++) scanf("%d", &y[i]);
	x[n] = X; y[m] = Y;
	puts(*max_element(x, x + n + 1) < *min_element(y, y + m + 1) ? "No War" : "War");
	return 0;
}

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

int main() {

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

}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define tt long t;cin>>t;while(t--)
#define tez ios_base::sync_with_stdio(false); cin.tie(NULL);
#define lli long long int
#define plli pair<lli,lli>
#define vlli vector<lli>
#define vplli vector<plli>
#define pqlli priority_queue <lli>
#define pqplli priority_queue <plli>
#define mplli map<lli,lli>
#define all(v) v.begin(),v.end()
#define alll(s) s.begin(),s.end(),s.begin(), ::tolower
#define allu(s) s.begin(),s.end(),s.begin(), ::toupper

#define mod 1000000007
#define ff first
#define ss second
#define fori(i,a,b)    for(int i=a;i<b;i++)
#define ford(i,a,b)    for(int i=a;i>=b;i--)
#define br cout<<endl
#define sz(v) (long)v.size()
#define YS cout<<"YES"<<endl
#define ys cout<<"yes"<<endl
#define Ys cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define no cout<<"no"<<endl
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define bs binary_search
#define mp make_pair
#define llmn LLONG_MIN
#define llmx  LLONG_MAX
#define stp setprecision
#define fxd fixed
#define tu (char)toupper
#define tl (char)tolower
#define coutv(v) for(lli index=0;index<v.size();index++) {cout<<v[index]<<" ";} br;

using namespace std;

/*
lli count01(string s,char ch){
  lli mx=0,c=0;
  if(ch=='0'){

   fori(i,0,sz(s)){
     if(s[i]=='0'){
        c++;}
     else{
        c=0;}
        if(c>mx){mx=c;}

   }

  }
  else{

    fori(i,0,sz(s)){
     if(s[i]=='1'){
        c++;}
     else{
        c=0;}
        if(c>mx){mx=c;}

    }

  }
return mx;

}*/
/*
vector<lli> prime(lli n){
  bool a[n+1];
  memset(a,true,sizeof(a));
  for(lli i=2;i*i<=n;i++){
    if(a[i]){
      for(lli j=i*i;j<=n;j+=i)
      {  a[j]=false;}
    }
  }
  vector<lli>v;
  for(lli i=2;i<=n;i++){
    if(a[i]){
      v.pb(i);
    }
  }
  return v;
}

*/

int main(){
tez
lli n=0,m;
cin>>n;
cout<<n+pow(n,2)+pow(n,3);




return 0;
}


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

using namespace std;

#define INF 1000000000
#define INFLL 0x3f3f3f3f3f3f3f3fLL 
#define EPS 10e-9
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define st first
#define nd second
#define sz(v) int(v.size())
#define all(X) (X).begin(), (X).end()
#define FOR(I, A, B) for(int I = A; I < B; I++)
#define RFOR(I, A, B) for(int I = A; I >= B; I--)

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<iii> viii;
typedef vector<ll> vll;

int n;
vi adjList[200100];
int dist[200100];
bool vis[200100];

void dfs(int u){
	vis[u] = true;
	for(int v : adjList[u]){
		if(vis[v]) continue;
		dist[v] = dist[u] + 1;
		dfs(v);
	}
}

int diameter(){
	dfs(1);
	int furthestNode = 0;
	FOR(i,1,n+1){
		if(dist[i] > dist[furthestNode]){
			furthestNode = i;
		}
	}
	memset(dist, 0, sizeof dist);
	memset(vis, false, sizeof vis);
	dfs(furthestNode);
	int ans = 0;
	FOR(i,1,n+1){
		ans = max(ans, dist[i]);
	}
	return ans;
}

int main(){
	cin >> n;
	FOR(i,0,n-1){
		int a, b;
		scanf("%d%d", &a, &b);
		adjList[a].pb(b);
		adjList[b].pb(a);
	}
	int d = diameter();
	printf("%s\n", (d-1)%3 ? "First" : "Second");
	return 0;
}

Measured memory_bytes: 18432
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
const int L = 1'000'000;
int A[L / 2 + 1];
int B[L / 2 + 1];
int main(){
  int i;
  while(getchar_unlocked() != '\n'){
  }
  int aa = 0;
  int bb = 0;
  int cc = 0;
  int mi = 0;
  int sum = 0;
  while(true){
    int c = getchar_unlocked();
    if(c == '(' || c == ')'){
      sum += (c == '(' ? +1 : -1);
      chmin(mi, sum);
    }
    else{
      int a = -mi;
      int b = sum - mi;
      if(a == b){
        chmax(cc, a);
      }
      if(a <  b){
        chmax(aa, a);
        A[a] += sum;
      }
      if(a >  b){
        chmax(bb, b);
        B[b] += sum;
      }
      mi = 0;
      sum = 0;
      if(c == EOF){
        break;
      }
    }
  }
  for(i=(0);i<(aa + 1);i++){
    chmin(mi, sum - i);
    sum += A[i];
  }
  chmin(mi, sum - cc);
  for(i=(bb + 1)-1;i>=(0);i--){
    sum += B[i];
    chmin(mi, sum - i);
  }
  puts(mi >= 0 && sum == 0 ? "Yes" : "No");
  return 0;
}
// cLay varsion 20200430-1

// --- original code ---
// const int L = 1'000'000;
// int A[L / 2 + 1], B[L / 2 + 1];
// {
// 	while(getchar_unlocked() != '\n') { }
// 	int aa = 0, bb = 0, cc = 0;
// 	int mi = 0, sum = 0;
// 	while(true) {
// 		int c = getchar_unlocked();
// 		if(c == '(' || c == ')') {
// 			sum += (c == '(' ? +1 : -1);
// 			mi <?= sum;
// 		} else {
// 			int a = -mi, b = sum - mi;
// 			if(a == b) { cc >?= a; }
// 			if(a <  b) { aa >?= a; A[a] += sum; }
// 			if(a >  b) { bb >?= b; B[b] += sum; }
// 			mi = 0; sum = 0;
// 			if(c == EOF) { break; }
// 		}
// 	}
// 	
// 	rep(i, aa + 1) {
// 		mi <?= sum - i;
// 		sum += A[i];
// 	}
// 	mi <?= sum - cc;
// 	rrep(i, bb + 1) {
// 		sum += B[i];
// 		mi <?= sum - i;
// 	}
// 	puts(mi >= 0 && sum == 0 ? "Yes" : "No");
// }


Measured memory_bytes: 3644
N = int(input())
XL = []
for i in range(N):
    XL.append(list(map(int, input().split())))
XL = list(map(lambda x: [x[0] - x[1], x[0] + x[1]], XL))
 
XL = sorted(XL, key=lambda x: x[1])

r = XL[0][1]
cnt = 1
for i in range(1, N):
    if XL[i][0] >= r:
        r = XL[i][1]
        cnt += 1
print(cnt)


Measured memory_bytes: 40996
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

lst=[[] for i in range(N+1)]

for a,b in AB:
    lst[a].append(b)
    lst[b].append(a)



used=set(list(range(1,N+1)))
value=-10**18
while used:
    a=used.pop()
    stack=[a]

    visited={a}
    while stack:
        a=stack.pop()
        for p in lst[a]:
            if p in used:
                used.remove(p)
            if not p in visited:
                visited.add(p)
                stack.append(p)
    value=max(len(visited),value)
print(value)


Measured memory_bytes: 166988
n = int(input())
a = list(map(int, input().split(" ")))



res1 = 0
sum = 0
# sei, hu, sei, hu....
# guu, ki, guu, ki
for i in range(n):
    sum += a[i]
    if sum <= 0 and i%2 == 0:
        res1 += abs(sum) + 1
        sum = 1
    elif sum >= 0 and i%2 == 1:
        res1 += abs(sum) + 1
        sum = -1
    # hutuunitoku


res2 = 0
sum = 0
# hu, sei, hu, sei....
# guu, ki, guu, ki
for i in range(n):
    sum += a[i]
    if sum <= 0 and i%2 == 1:
        res2 += abs(sum) + 1
        sum = 1
    elif sum >= 0 and i%2 == 0:
        res2 += abs(sum) + 1
        sum = -1
    # hutuunitoku

print(min(res1, res2))


Measured memory_bytes: 20440
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define trav(x,A) for(auto &x:A)
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef vector<int> veci;
typedef vector<long long> vecl;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);

//Required Functions

ll power(ll x,ll y) 
{ 
	if (y == 0) 
		return 1; 
	ll p = power(x, y/2) % MOD; 
	p = (p * p) % MOD; 
  
	return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
	#ifndef ONLINE_JUDGE
	if (fopen("INPUT.txt", "r"))
	{
		freopen ("INPUT.txt" , "r" , stdin);
		//freopen ("OUTPUT.txt" , "w" , stdout);
	}
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	clock_t clk;
	clk = clock();
//-----------------------------------------------------------------------------------------------------------//

	READV(X);
	READV(Y);
	READV(Z);
	swap(X,Y);
	swap(X,Z);
	cout<<X<<" "<<Y<<" "<<Z<<endl;

//-----------------------------------------------------------------------------------------------------------//


	clk = clock() - clk;
	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

	return 0;
}

Measured memory_bytes: 256
def is_tree(g, n):
    visiteds = [False] * n
    q = [0]
    while q:
        i = q.pop()
        if visiteds[i]:
            continue
        visiteds[i] = True
        for to in g[i]:
            if not visiteds[to]:
                q.append(to)
    return all(visiteds)


def main():
    global n
    n, m = map(int, input().split())
    g = [set() for _ in range(n)]
    es = []
    for _ in range(m):
        a, b = map(lambda s: int(s) - 1, input().split())
        g[a].add(b)
        g[b].add(a)
        es.append((a, b))

    res = 0
    for a, b in es:
        g[a].remove(b)
        g[b].remove(a)
        if not is_tree(g, n):
            res += 1
        g[a].add(b)
        g[b].add(a)

    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
using namespace std;
 
void isort(std::vector<int> vec){
    for(int i=0;i<vec.size();++i){
        auto v = vec[i];
       
        int j=i-1;
        for (j; j>=0; --j ){
            if(vec[j]<=v) break;
            vec[j+1] = vec[j];
        }
        vec[j+1] = v;
 
        for(auto& a:vec) cout<<a<<((&a!=&vec.back())? " ":"\n");
    }
} 
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
     
    int nb; cin>>nb;
    std::vector<int> cards; cards.resize(nb);
    for(auto& a:cards) cin>>a;
    isort(cards);
}

Measured memory_bytes: 3188
#include <iostream>
	#include <iomanip>
	#include<math.h>
	#include<list>
	#include <algorithm>
	#include<set>
	#include<vector>
	#include<math.h>
	#include<map>
	#include<string>
	#include <numeric>
	#include <queue>
	#include <sstream>
	#include <bitset>
	#include<stack>

	using namespace std;
	using ll = long long;
	using vll = vector<long long>;
	using sll = set<long long>;


	template<typename T>
	T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
	template<typename T>
	T lcm(T a, T b) { return a / gcd(a, b) * b; }

	template<typename T>
	map<T, T> getPrimeFactor(T n) {
		map<T, T> res;
		for (T i = 2; i * i <= n; ++i) {
			while (n % i == 0) {
				res[i] ++;
				n /= i;
			}
		}
		if (n != 1) res[n] = 1;
		return res;
	}

	template<typename T>
	bool IsPrimeNumber(T num)
	{
		if (num <= 2) return true;
		else if (num % 2 == 0) return false;

		double sqrtNum = sqrt(num);
		for (int i = 3; i <= sqrtNum; i += 2)
		{
			if (num % i == 0)
			{
				return false;
			}
		}

		return true;
	}

	long long modinv(long long a, long long m) {
		long long b = m, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= m;
		if (u < 0) u += m;
		return u;
	}

	// 繰り返し二乗法
	ll pow2(ll n, ll p, ll mod) {
		if (p == 0 || n == 1) {
			return 1;
		}
		else {
			ll ret = pow2(n * n % mod, p / 2, mod);
			if (p % 2 == 1) {
				ret *= n;
			}
			return ret % mod;
		}
	}


	#define rep(i,s,e) for(ll i=s;i<e;i++)
	#define repeq(i,s,e) for(ll i=s;i<=e;i++)

	int main() {
		ll N, K;
		cin >> N >> K;
		vll A(N);
		vll sum(N + 1, 0);
		rep(i, 0, N) {
			cin >> A[i];
			sum[i + 1] += sum[i] + A[i];
			if (i >= K) {
				if (sum[i + 1] - sum[i + 1 - K] > sum[i] - sum[i - K]) {
					cout << "Yes" << endl;
				}
				else {
					cout << "No" << endl;
				}
			}
		}
		return 0;
	}


Measured memory_bytes: 6420
#include <iostream>
#include <vector>
#include <numeric>

int main() {
	int n = 0;
	std::cin >> n;

	//int l, i = 0;
	std::vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		std::cin >> a[i];
	}
	
	std::vector<int> tf(n);


	for (int j = 0; j < n; j++) 
	{
		tf[j] = (a[j] == (j + 1)) ? 0 : 1;
		//std::cout << a[j] << " " << tf[j] << std::endl;
	}

	int sum = std::accumulate(tf.begin(), tf.end(), 0);
	//std::cout << sum << std::endl;

	if (sum == 0 || sum == 2)
	{
		std::cout << "YES" << std::endl;
	}
	else
	{
		std::cout << "NO" << std::endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
    char s[20],t[20];
    scanf("%s",s);
    scanf("%s",t);
    int i;
    int n=strlen(s);
    s[n]=t[n];
    for(i=0;i<strlen(t);i++)
    {
        if(s[i]!=t[i])
        {
            printf("No");
            return 0;
        }
    }
    printf("Yes");
    return 0;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
using namespace std;
using ll = long long;
int main(){
  int k,n;
  cin >>n;
  k=n;
  int keta=1;
  while(k/10!=0){
    k /=10;
    keta+=1;
  }
  if(keta==1) cout << n;
  if(keta==2) cout << 9;
  if(keta==3) cout << 9 + n - 99;
  if(keta==4) cout << 909;
  if(keta==5) cout << 909 + n -9999;
  if(keta==6) cout << 90909;
  return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;
constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

int G[201][201];

int mygcd(int a, int b) {
    if(G[a][b]) return G[a][b];
    return G[a][b] = G[b][a] = __gcd(a, b);
}

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

    int k;
    cin >> k;
    ll ans = 0;
    FOR(i, 1, k + 1)
    FOR(j, 1, k + 1) FOR(l, 1, k + 1) ans += mygcd(i, mygcd(j, l));

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3772
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
//const long double EPS = 1e-14;
const int INF = (1<<30)-1;
const ll LINF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
//template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main () {
  int n;
  cin >> n;
  vi p(n);
  rep(i,n) cin >> p[i];
  
  int ans = 0;
  int mi = INF;
  rep(i,n) {
    chmin(mi, p[i]);
    if (mi == p[i]) ans++;
  }

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

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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

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

    int H, W;
    cin >> H >> W;
    int N;
    cin >> N;
    Vi a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    vector<Vi> ans(H, Vi(W));
    int color = 1;
    for (int i = 0; i < H; i++) {
        if (i & 1) {
            for (int j = W - 1; j >= 0; j--) {
                ans[i][j] = color;
                --a[color - 1];
                if (a[color - 1] == 0) {
                    ++color;
                }
            }
        }
        else {
            for (int j = 0; j < W; j++) {
                ans[i][j] = color;
                --a[color - 1];
                if (a[color - 1] == 0) {
                    ++color;
                }
            }
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W - 1; j++) {
            cout << ans[i][j] << ' ';
        }
        cout << ans[i][W - 1] << '\n';
    }

    return 0;
}

Measured memory_bytes: 384
n, m = [int(x) for x in input().split()]
ablist = []
for i in range(n):
    ablist.append([int(x) for x in input().split()])
ablist.sort()
count = 0
cost = 0
for i in range(n):
    count += ablist[i][1]
    cost += ablist[i][0] * ablist[i][1]
    if count >= m:
        cost -= ablist[i][0] * (count - m)
        break
print(cost)

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

using namespace std;
string max_s(string a,string b)
{
    if(a.length()>b.length())
        return a;
    return b;
}
int main() {
    string a, b;
    cin >> a >> b;
    int dp[a.length() + 1][b.length() + 1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=a.length();i++)
    for(int k=1;k<=b.length();k++)
    {
        if(a[i-1]==b[k-1])
        {
            dp[i][k]=dp[i-1][k-1]+1;
        } else
        {
            dp[i][k]=max(max(dp[i-1][k],dp[i][k-1]),dp[i-1][k-1]);
        }
    }
    string answer="";
    int k=b.length();
    int i=a.length();
       while(k>0&&i>0)
       {
           if(dp[i][k]==dp[i][k-1])
           k--;
           else if(dp[i][k]==dp[i-1][k])
           i--;
           else
           {
               answer=a[i-1]+answer;
               i--;
               k--;
           }

       }
       cout<<answer;

}


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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    using bits = bitset<17>;
    int n; cin >> n;
    int x, y; cin >> x >> y;
    bits a = x, b = y;
    if ((a.count() + b.count()) % 2 == 0) {
        cout << "NO\n";
        return 0;
    }
    int sw = -1;
    auto bitswap = [&](auto a, auto b) -> void {
        bool c = a; a = b; b = c;
    };
    for (int i = n-1; i >= 0; i--) {
        if (a[i] != b[i]) {
            sw = i;
            bitswap(a[n-1], a[i]);
            bitswap(b[n-1], b[i]);
            break;
        }
    }
    auto bv = [&](int n) {
        vector<bits> v; bits msk = 0;
        v.emplace_back(msk);
        for (int i = 0; i < n; i++) {
            msk[i] = 1;
            int c = v.size();
            for (int j = c-1; j >= 0; j--) {
                bits w = v[j]; w[i] = 1;
                v.emplace_back(w);
            }
        }
        v.emplace_back(0);
        reverse(v.begin(), v.end());
        return v;
    };

    vector<bits> ans; bits curr = a;
    for (int i = n-1; i >= 0; i--) {
        assert(curr[i] != b[i]);
        int s = (i && curr[i-1] == b[i-1]) ? i-1 : 0;
        auto v = bv(i);
        for (int j = 0; j < (1 << i); j++) {
            bits w = v[j];
            bitswap(w[s], w[0]);
            ans.emplace_back(w ^ curr);
        }
        curr = ans.back();
        curr[i] = !curr[i];
    }
    ans.emplace_back(curr);
    cout << "YES\n";
    for (int i = 0; i < (1 << n); i++) {
        auto &c = ans[i];
        bitswap(c[sw], c[n-1]);
        if (i) cout << " "; 
        cout << c.to_ulong();
    }
    cout << "\n";
    return 0;
}

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

int main() {
  int64_t A;
  double b;
  cin >> A >> b;
  if (A == 0 || b == 0) {
    cout << 0 << endl;
  }
  else {
    int64_t B = b*100+0.5;
    int64_t C = A*B/100;
    cout << C << endl;
  }
}


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

using namespace std;

int main () {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    set<int> s;
    for (int i = 0; i < 3; ++i) {
      int x; cin >> x; s.insert(x);
    }cout << s.size() << '\n';
    
    return 0;
}



Measured memory_bytes: 3612
n,k = gets.split.map &:to_i
h = gets.split.map &:to_i

INF = 10**12
dp = Array.new(n,INF)
dp[0] = 0

1.upto(n-1) do |i|
  min = 10000000001
  t = i - k
  t = 0 if t < 0
  t.upto(i-1) do |j|
    cost = (h[i] - h[j]).abs + dp[j]
    min = cost if min > cost
  end
  dp[i] = min
end

puts dp[-1]


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

using namespace std;

typedef long long	ll;

const int N = int(1e5 + 10);
const int mod = ll(1e9) + 7;
ll dp[N];

ll fast_expo(ll x, ll e, ll mod){
	ll b = x;
	ll r = 1LL;

	while(e){
		if(e & 1){
			r = (r * b) % mod;
		}

		b = (b * b) % mod;
		
		e >>= 1LL;
	}

	return r;
}

ll solve(int n, int k, ll g){
	if(n == 0){
		return g;
	}

	ll sum = 0LL;

	for(ll d = 1LL ; d <= k ; d++){
		sum += solve(n - 1, k, __gcd(g, d));
	}

	return sum;
}

int main(){
	int n;
	ll k;

	scanf("%d", &n);
	scanf("%lld", &k);

	ll sum = 0LL;

	for(ll d = k ; d >= 1LL ; d--){
		ll div = k / d;

		dp[d] = fast_expo(div, n, mod);

		for(ll e = 2LL * d ; e <= k ; e += d){
			dp[d] -= dp[e];

			if(dp[d] < 0){
				dp[d] += mod;
			}
		}

		// printf("%lld %lld\n", d, dp[d]);

		ll add = (dp[d] * d) % mod;
		// dp[d] = (dp[d] * d) % mod;
	
		sum += add;

		if(sum >= mod){
			sum -= mod;
		}
	}

	printf("%lld\n", sum);

	return 0;
}

Measured memory_bytes: 4492
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int a,b;
    cin>>a>>b;
    char g[100][101]={};
    rep(i,50){
        rep(j,100){
            g[i][j]='#';
        }
    }
    Rep(i,50,100){
        rep(j,100){
            g[i][j]='.';
        }
    }
    a--,b--;
    for(int i=1;a&&i<50;i+=2){
        for(int j=1;a&&j<100;j+=2){
            g[i][j]='.';
            a--;
        }
    }
    for(int i=51;b&&i<100;i+=2){
        for(int j=1;b&&j<100;j+=2){
            g[i][j]='#';
            b--;            
        }
    }
    cout<<100<<" "<<100<<endl;
    rep(i,100)cout<<g[i]<<endl;
}

Measured memory_bytes: 256