akhauriyash/Code-Regression huggingface dataset:
class DoubleLinkedListItem
	attr_reader :previous_item, :next_item, :key
	attr_writer :previous_item, :next_item, :key
	
	def initialize(key)
		@previous_item = nil
		@next_item = nil
		@key = key
	end
end

class DoubleLinkedList
	attr_reader :head, :tail
	attr_writer :head, :tail

	def initialize
		@head = nil
		@tail = nil
	end
	
	def insert(key)
		tmp = DoubleLinkedListItem.new(key)
		if self.head == nil then
			self.head = tmp
			self.tail = tmp
		elsif self.head.next_item == nil then
			self.head = tmp
			self.head.next_item = self.tail
			self.tail.previous_item = self.head
		else
			tmp.next_item =  self.head
			self.head.previous_item = tmp
			self.head = tmp
		end
	end
	
	def delete(key)
		deleted = false
		if self.head.key == key then
			self.deleteFirst
			deleted = true
		else
			iterator = self.head.next_item
			until iterator == self.tail do
				if iterator.key == key then
					iterator.previous_item.next_item = iterator.next_item
					iterator.next_item.previous_item = iterator.previous_item
					iterator.previous_item = nil
					iterator.next_item = nil
					deleted = true
					break
				else
					iterator = iterator.next_item
				end
			end
		end
		if deleted == false && self.tail.key == key then
			self.deleteLast
		end
	end
	
	def deleteFirst
		tmp = self.head
		if self.head == self.tail then
			self.head.next_item = nil
			self.head.previous_item = nil
			self.head = nil
			self.tail = nil
		else
			self.head.next_item.previous_item = nil
			self.head = self.head.next_item
			tmp.next_item = nil
			tmp.previous_item = nil
		end
	end
	
	def deleteLast
		tmp = self.tail
		if self.head == self.tail then
			self.head.next_item = nil
			self.head.previous_item = nil
			self.head = nil
			self.tail = nil
		else
			self.tail.previous_item.next_item = nil
			self.tail = self.tail.previous_item
			tmp.next_item = nil
			tmp.previous_item = nil
		end
	end
	
	def show
		iterator = self.head
		until iterator == self.tail do
			print iterator.key, " "
			iterator = iterator.next_item
		end
		print iterator.key, "\n"
	end
end

dll = DoubleLinkedList.new()
n = STDIN.gets.chomp.to_i

0.upto(n-1) { |i|
	command_line = STDIN.gets.chomp.split (' ')
	
	dll.insert(command_line[1].to_i) if :"#{command_line[0]}" == :insert
	dll.delete(command_line[1].to_i) if :"#{command_line[0]}" == :delete
	dll.deleteFirst if :"#{command_line[0]}" == :deleteFirst
	dll.deleteLast  if :"#{command_line[0]}" == :deleteLast
}

dll.show


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

long long int gcd(long long int a, long long int b){
    return b != 0 ? gcd(b, a % b) : a;
}

long long int lcm(long long int a, long long int b){
    return a * b / gcd(a, b);
}

int main()
{
    long long int A, B, C, D, F, G;
    cin >> A >> B >> C >> D;
    long long int E = lcm(C, D);
    A = A - 1;
    F = B - B / C - B / D + B / E;
    G = A - A / C - A / D + A / E;
    F = F - G;
    cout << F << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int a,b;
    cin>>a>>b;
    if(a>b)
    cout<<a+(a-1);
    else if(b>a)
    cout<<b+(b-1);
    else
    cout<<a+b;
}

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

int main()
{
	int n;
	cin >> n;
	long long int L[100];
	L[0] = 2;
	L[1] = 1;
	for (int i = 2; i < 87; ++i)
	{
		L[i] = L[i-1] + L[i-2];
	}
	cout << L[n] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;


int main(void) {
    string s;
    cin >> s;
    if(s == "Sunny") {
        cout << "Cloudy" << endl;
    } else if (s == "Cloudy") {
        cout << "Rainy" << endl;
    } else {
        cout << "Sunny" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
d, g = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(d)]

def dfs(d, rest): # difficulty, rest score
    if d <= 0: return 10**9
    num, bonus = data[d-1] # num of problems, bonus
    # now, use or don't use difficulty d?
    use = min(rest//(d*100), num) # num when use
    score = use * d * 100 # score when use
    if use == num: score += bonus # ?perfect
    if rest - score > 0: # ?rest
        use += dfs(d-1, rest - score) # rest of score -> recursion
    not_use = dfs(d-1, rest) # num when don't use -> recursion
    return min(use, not_use)

print(dfs(d, g))


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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++)
    cin >> a.at(i);
  
  sort(a.begin(),a.end());
  
  long long int k=250000;
  
  for(int p=a.at(0);p<=a.at(n-1);p++){
    long long int c=0;
    
    for(int i=0;i<n;i++){
      c+=(a.at(i)-p)*(a.at(i)-p);
    }
    
    k=min(k,c);
  }
  cout << k << endl;
}

Measured memory_bytes: 256
main :: IO ()
main = do
  [n, m] <- (map read . words) <$> getLine :: IO [Int]
  -- すべてのケースに正解する確率の逆数
  let pPass = 2^m
  -- すべてのケースが終了するまでにかかる時間
      l = 1900 * m + 100 * (n - m)
  print $ pPass * l


Measured memory_bytes: 508
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
		if len(os.Args) > 2 {
			wfp, _ = os.Create(os.Args[2])
		}
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)

	ans := "second"
	for i := 0; i < n; i++ {
		a := getNextInt(scanner)
		if a%2 == 1 {
			ans = "first"
			break
		}
	}
	fmt.Fprintln(writer, ans)
	writer.Flush()
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int a[N];
int main()
{
    int n;
    scanf("%d",&n);
    double all=0,val;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        all+=a[i];
    }
    all/=n;
    val = fabs(all-a[0]);
    int ans = 0;

    for(int i=1;i<n;i++)
    {
        if(fabs(fabs(all-a[i])-val)<=0.00001)
            continue;
        if(fabs(all-a[i])<val)
        {
            ans =i;
            val=fabs(all-a[i]);
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
import heapq
from collections import defaultdict


def read():
    X, Y, Z, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    B = list(map(int, input().strip().split()))
    C = list(map(int, input().strip().split()))
    return X, Y, Z, K, A, B, C


def solve(X, Y, Z, K, A, B, C, INF=10000000001):
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    
    used = defaultdict(bool)
    h = []
    p, q, r = 0, 0, 0
    heapq.heappush(h, (-A[p] - B[q] - C[r], p, q, r))
    used[(p, q, r)] = True
    for k in range(K):
        a, p, q, r = heapq.heappop(h)
        print(-a)
        if p+1 < len(A) and not used[(p+1, q, r)]:
            heapq.heappush(h, (-A[p+1] - B[q] - C[r], p+1, q, r))
            used[(p+1, q, r)] = True
        if q+1 < len(B) and not used[(p, q+1, r)]:
            heapq.heappush(h, (-A[p] - B[q+1] - C[r], p, q+1, r))
            used[(p, q+1, r)] = True
        if r+1 < len(C) and not used[(p, q, r+1)]:
            heapq.heappush(h, (-A[p] - B[q] - C[r+1], p, q, r+1))
            used[(p, q, r+1)] = True


if __name__ == '__main__':
    inputs = read()
    solve(*inputs)


Measured memory_bytes: 10768
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */
pair<int, int> culc(vector<vector<int>> a, vector<bool> canUse) {

  int n = a.size();
  int m = a[0].size();
  vector<int> score(m, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (!canUse[a[i][j]]) continue;
      score[a[i][j]]++;
      break;
    }
  }

  int val = 0;
  int id;
  for (int i = 0; i < m; i++) {
    if (val < score[i]) {
      val = score[i];
      id = i;
    }
  }

  return make_pair(val, id);
}

int main() {
  
  int n, m; cin >> n >> m;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
      a[i][j]--;
    }
  }
  
  vector<bool> canUse(m, true);
  int ans = n + 1;
  while (1) {

    // 全部使えないなら，終わり
    bool end = true;
    for (int i = 0; i < m; i++) {
      if (canUse[i]) end = false;
    }
    if (end) break;

    int tmp;
    int id;
    tie(tmp, id) = culc(a, canUse);
    ans = min(ans, tmp);
    canUse[id] = false;
  }

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


Measured memory_bytes: 1028
#include <stdio.h>

int main(){
  int h, w;  scanf("%d %d", &h, &w);
  int field[55][55] = {0}, white = 0;
  for(int i=0; i<h; i++){
    char s[55];  scanf("%s", s);
    for(int j=0; j<w; j++)
      if(s[j] == '.'){
	field[i+1][j+1] = 1;
	white++;
      }
  }
  int table[55][55] = {0};  table[1][1] = 1;
  int queue[2550][2] = {0}, front = 0, rear = 0;
  queue[rear][0] = 1, queue[rear][1] = 1, rear++;
  while(front != rear){
    int nowh, noww;
    nowh = queue[front][0], noww = queue[front][1], front = (front+1)%2550;
    for(int s=-1; s<=1; s+=2){
      if(field[nowh+s][noww] && !table[nowh+s][noww]){// || table[nowh+s][noww]>table[nowh][noww]+1)){
	table[nowh+s][noww] = table[nowh][noww] + 1;
	queue[rear][0] = nowh+s, queue[rear][1] = noww, rear = (rear+1)%2550;
      }
      if(field[nowh][noww+s] && !table[nowh][noww+s]){
	table[nowh][noww+s] = table[nowh][noww] + 1;
	queue[rear][0] = nowh, queue[rear][1] = noww+s, rear = (rear+1)%2550;
      }
    }
  }

  int ans;
  if(table[h][w])  ans = white - table[h][w];
  else             ans = -1;
  printf("%d\n", ans);
  
  return 0;
}


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


int main()
{	
	int a,b,c,d,ans=0;
	cin>>a>>b>>c>>d;
	for(int i=0;i<=100;i++)
	{
		if(a<i&&i<=b&&c<i&&i<=d)ans++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
MAX = 50001

is_prime = [True for _ in range(MAX)]
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX ** (1 / 2)) + 1):
  if is_prime[i]:
    for j in range(i ** 2, MAX, i):
      is_prime[j] = False

primes = [i for i in range(MAX) if is_prime[i]]

def main():
  while True:
    n = int(input())
    if not n:
      break
        
    ans = 0
    for i in primes:
      if i > n // 2:
        break
      if is_prime[n - i]:
        ans += 1
  
    print(ans)

main()


Measured memory_bytes: 6068
r1,c1,r2,c2 = map(int,input().split())


def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return (fact[n] * factinv[r] * factinv[n-r])%mod

mod=10**9 + 7
fact=[1,1]
factinv=[1,1]
inv=[0,1]
N=r2+c2+3
mod=10**9+7
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
    
#二次元累積和もどき，i,jのマスを考える，
a=cmb(r2+c2+2,r2+1,mod) 
b=cmb(r1+c2+1,r1,mod)
c=cmb(r2+c1+1,c1,mod)
d=cmb(r1+c1,r1,mod)
ans=a-b-c+d
print(ans%mod)




Measured memory_bytes: 133036
#include<bits/stdc++.h>
using namespace std;
void solving(){
    int n;
    cin>>n;
    int u=n-1,j=n+2;
    int a[u],b[j];
    memset(b,0,(j)*sizeof(b[0]));
    for(int i=0;i<n-1;i++){
        cin>>a[i];
        b[a[i]]++;}
        for(int i=1;i<=n;i++)cout<<b[i]<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
solving();
return 0;
}


Measured memory_bytes: 5224
from collections import deque
N,M=map(int,input().split())
S=list(input()) #S[0]....S[N]
flag=1
done=0
piv=N
ans=deque()
while flag==1:
    done=0
    for i in range(max(0,piv-M),piv):
        if S[i]=="0":
            ans.appendleft(piv-i)
            piv=i
            done=1
            break
    if piv==0:
        break
    if done==0:
        flag=0
        break
    #print(piv,ans)
#print(flag)
if flag==1:
    print(*ans)
else:
    print("-1")

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

class Program
{
    static void Main(string[] args)
    {
        int[] abcd = Console.ReadLine().Select(s => int.Parse(s.ToString())).ToArray();
        for (int i = 0; i < 8; i++)
        {
            string res = abcd[0].ToString();
            int t = abcd[0];
            int flag = i;
            for (int j = 0; j < 3; j++)
            {
                if (0 < (flag & 1))
                {
                    res += "+" + abcd[j + 1];
                    t += abcd[j + 1];
                }
                else
                {
                    res += "-" + abcd[j + 1];
                    t -= abcd[j + 1];
                }
                flag >>= 1;
            }
            if (t == 7)
            {
                Console.WriteLine(res + "=7");
                return;
            }
        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
  
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        
const int  N = 2e5 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const long long LINF = 1e18 + 3141;
int dp[N];
vector <int> g[N];
int s[N];
int n, m;
vector<int> ans;
int used[N];
void dfs (int v) {
	used[v] = true;
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (!used[to])
			dfs (to);
	}
	ans.push_back (v);
}
 
void topological_sort() {
	for (int i = 1; i <= n; ++i)
		if (!used[i])
			dfs (i);
	reverse (ans.begin(), ans.end());
}
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
    }
    topological_sort();
    for(int i = ans.size() - 2; i >= 0; --i){
        int cur = ans[i]; 
        for(int v : g[cur]){
            dp[cur] = max(dp[cur], dp[v] + 1);
        }
    }
    cout << *max_element(dp + 1, dp + n + 1);
}
 
int main(){
    speed();
    int t = 1;

    // cin >> t;
    while(t--)solve();
}

Measured memory_bytes: 10744
#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
int C[MAXN],S[MAXN],F[MAXN];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&C[i],&S[i],&F[i]);
        }
        for(int i=0;i<n;i++)
        {
            int t=0;
            for(int j=i;j<n-1;j++)
            {
                if(t<S[j])       t=S[j];
                else if(t%F[j])  t=t+F[j]-t%F[j];
                t+=C[j];
            }
            printf("%d\n",t);
        }
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
			
			long a = sc.nextLong();
			long b = sc.nextLong();
			long c = sc.nextLong();
			long d = sc.nextLong();

			long ac=a*c;
			long ad=a*d;
			long bc=b*c;
			long bd=b*d;
			if(ac>ad) {
				if(bc>bd) {
					System.out.println(ac>bc?ac:bc);					
				}else {
					System.out.println(ac>bd?ac:bd);					
				}
			}else {
				if(bc>bd) {
					System.out.println(ad>bc?ad:bc);					
				}else {
					System.out.println(ad>bd?ad:bd);					
				}				
			}
	}	
}

Measured memory_bytes: 35856
def main():
    A = 1
    B = 0
    C = 0
    while True:
        try:
            cup_1,cup_2 = input().split(",")

            if cup_1 == 'A' and cup_2 == 'B' or cup_1 == 'B' and cup_2 == 'A':
                A,B = B,A
            elif cup_1 == 'B' and cup_2 == 'C' or cup_1 == 'C' and cup_2 == 'B':
                B,C = C,B
            elif cup_1 == 'A' and cup_2 == 'C' or cup_1 == 'C' and cup_2 == 'A':
                A,C = C,A
        except EOFError:
            break
    if A:
        print('A')
    elif B:
        print('B')
    elif C:
        print('C')

if __name__ == '__main__':
    main()


Measured memory_bytes: 5564
using System;
using System.Collections.Generic;
using System.Linq;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int>inputs=Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
            int n =inputs[0];
            int a =inputs[1];
            int b =inputs[2];
            var ans=(n*a)>b?b:(n*a);
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 11220
package main

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

var (
	scanner = bufio.NewScanner(os.Stdin)
	w       = bufio.NewWriter(os.Stdout)
)

const M = 10000000

type Dict struct {
	dict []bool
}

func readInt() (read int) {
	scanner.Scan()
	read, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return
}

func readString() string {
	scanner.Scan()
	return scanner.Text()
}

func getChar(ch rune) int {
	switch ch {
	case 'A':
		return 1
	case 'C':
		return 2
	case 'G':
		return 3
	}
	// 'T'
	return 4
}

func getKey(s string) int {
	keys := []rune(s)
	return h2(h1(keys))
}

func h1(keys []rune) int {
	sum := 0
	p := 1
	for i := 0; i < len(keys); i++ {
		sum += p * (getChar(keys[i]))
		p *= 5
	}
	return sum
}

func h2(key int) int {
	return key % M
}

func (d *Dict) find(s string) bool {
	key := getKey(s)
	return d.dict[key] == true
}

func (d *Dict) insert(s string) {
	key := getKey(s)
	d.dict[key] = true
}

func main() {
	scanner.Split(bufio.ScanWords)
	defer w.Flush()

	n := readInt()

	d := Dict{make([]bool, M)}

	for i := 0; i < n; i++ {
		cmd := readString()
		v := readString()
		if cmd == "insert" {
			d.insert(v)
		} else {
			if d.find(v) {
				fmt.Fprintln(w, "yes")
			} else {
				fmt.Fprintln(w, "no")
			}
		}
	}
}




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

int main(){
	string s;
	cin >> s;
	
	string ans;
	if(s=="Sunny")		ans="Cloudy";
	else if(s=="Cloudy")	ans="Rainy";
	else			ans="Sunny";
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
//---------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#include<algorithm>
//---------------------------------------------------------------
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define SIZE 100005
#define INF 1000000000000000LL
#define all(x) x.begin(),x.end()
#define fi first
#define se second
using pint = pair<int,int>;
using vec = vector<int>;
using ll=long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
//---------------------------------------------------------------
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
//---------------------------------------------------------------

//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓


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

    int n,k;cin>>n>>k;
    vec s(n+1);
    rep(i,k){
        int d;
        cin>>d;
        rep(j,d){
            int a;
            cin>>a;
            s[a]++;
        }
    }

    int cnt=0;
    rep1(i,n){
        if(s[i]==0){
            cnt++;
        }
    }

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

Measured memory_bytes: 3560
#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <numeric>
#include <functional>

intmax_t hoge(const std::vector<intmax_t>& A, const std::vector<intmax_t>& B) {
  std::vector<intmax_t> gt, lt;
  size_t N = A.size();
  for (size_t i = 0; i < N; ++i) {
    if (A[i] < B[i]) {
      lt.push_back(B[i]-A[i]);
    } else if (A[i] > B[i]) {
      gt.push_back(A[i]-B[i]);
    }
  }

  std::sort(lt.begin(), lt.end());
  std::sort(gt.begin(), gt.end());
  std::vector<intmax_t> f(gt.size(), 1);
  intmax_t res = lt.size();
  while (!gt.empty() && !lt.empty()) {
    intmax_t ll = lt.back();
    intmax_t gg = gt.back();
    if (gg >= ll) {
      lt.pop_back();
      gt.back() -= ll;
      res += f.back();
      f.back() = 0;
      if (gt.back() == 0) {
        gt.pop_back();
        f.pop_back();
      }
    } else {
      lt.back() -= gg;
      gt.pop_back();
      res += f.back();
      f.pop_back();
    }
  }
  if (!lt.empty()) return -1;
  return res;
}

int main() {
  size_t N;
  scanf("%zu", &N);

  std::vector<intmax_t> A(N), B(N);
  for (auto& a_i: A) scanf("%jd", &a_i);
  for (auto& b_i: B) scanf("%jd", &b_i);

  {
    intmax_t SA = std::accumulate(A.begin(), A.end(), 0L);
    intmax_t SB = std::accumulate(B.begin(), B.end(), 0L);
    if (SA < SB)
      return puts("-1"), 0;
  }
  {
    bool valid = true;
    for (size_t i = 0; i < N; ++i)
      if (A[i] < B[i]) {
        valid = false;
        break;
      }
    if (valid)
      return puts("0"), 0;
  }

  printf("%jd\n", hoge(A, B));
}


Measured memory_bytes: 3188
N,K = map(int,input().split())

senbei = [0] * K
i = 0

while N > 0:
  senbei[i] += 1
  N -= 1
  if i == K - 1:
    i = 0
  else:
    i += 1
    
print(max(senbei) - min(senbei))

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

long long cal(long long A){
    A++;
    long long ans = 0;
    for (int i = 0; i < 40; i++)
    {
        long long loop = 1ll << (i + 1);
        long long cnt = A / loop * (loop / 2);
        cnt += max(0ll, A % loop - loop / 2);
        if(cnt % 2 == 1){
            ans += 1ll << i;
        }
    }
    return ans;
}

int main() {
    long long  A, B;
    cin >> A >> B;

    long long ans = cal(A-1) ^ cal(B);

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>
#include <cmath>
#include <string>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
using namespace std;
//================================================

int a = 0, b = 0, c, d, n, k = 0;
string s, t;



int main()
{
	 ll n, m;
	cin >> n >> m;
	if (n >= 2 && m >= 2)
		cout << (n - 2) * (m - 2) << endl;
	else if (n == 1 && m >= 2)
		cout << m - 2 << endl;
	else if (n >= 2 && m == 1)
		cout << n - 2 << endl;
	else
		cout << 1 << endl;


	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner

object Main {
  val sc = new Scanner(System.in)
  def main(args: Array[String]): Unit = {
    val a = sc.nextInt
    val b = sc.nextInt
    val c = sc.nextInt
    val d = sc.nextInt
    val e = sc.nextInt
    val k = sc.nextInt

    val res = if(e - a <= k) "Yay!" else ":("

    println(res)
  }
}

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

int n,a[100010],b[100010],k[100010],w[100010],suma,sumb,cnt,ans;
vector<pair<int,int> > v;

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a[i];suma+=a[i];}
	for(int i=1;i<=n;i++){cin>>b[i];sumb+=b[i];}
	if(suma<sumb){
		cout<<-1<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(a[i]>=b[i]){
			k[i]=a[i]-b[i];
		}
		else k[i]=-1;
	}
	for(int i=1;i<=n;i++){
		if(k[i]>0) v.push_back(make_pair(k[i],i));
	}
	sort(v.begin(),v.end());
	int cnt=v.size()-1;
	for(int i=1;i<=n;i++){
		if(k[i]==-1){
			w[i]=1;
			int val=b[i]-a[i];
			while(val>0&&cnt>=0){
				int cur=v[cnt].first;
				if(cur>val){
					v[cnt].first-=val;
					w[v[cnt].second]=1;
					break;
				}
				else{
					val-=cur;
					w[v[cnt].second]=1;
					cnt--;
				}
			}
		}
	}
	for(int i=1;i<=n;i++) ans+=w[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4340
#include<iostream>
#include<queue>
using namespace std;
int main(){
	int n=0;
	int i=0;
	priority_queue<int,vector<int>,greater<int> > q1;
	for(i=0;i<3;i++){
		cin>>n;
		q1.push(n);
	}
	for(i=0;i<2;i++){
		cout<<q1.top()<<" ";
		q1.pop();
	}
	cout<<q1.top()<<endl;
}

Measured memory_bytes: 1212
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
const ll MOD=1000000007;
const ll INF=1<<27;
int n,a,b,c;
vector<int> l(10);
int ans=INF;
void dfs(int depth,vector<int> v){
    if(depth==n){
        if(find(all(v),0)==v.end()||find(all(v),1)==v.end()||find(all(v),2)==v.end())return;
        else {
            vector<int> sum(3,0);
            vector<int> cnt(3,0);
            for(int i=0;i<n;i++){
            if(v[i]==0)sum[0]+=l[i],cnt[0]++;
            if(v[i]==1)sum[1]+=l[i],cnt[1]++;
            if(v[i]==2)sum[2]+=l[i],cnt[2]++;
            }
             int ret=0;
             int tmp=0;
             tmp=(cnt[0]-1)+(cnt[1]-1)+(cnt[2]-1);
               ret=abs(a-sum[0])+abs(b-sum[1])+abs(c-sum[2])+10*tmp;
               ans=min(ans,ret);
               return;
        }
    }
    for(int i=0;i<4;i++){
        v[depth]=i;
        dfs(depth+1,v);
    }
}
int main(){
 cin>>n>>a>>b>>c;
 l.resize(n);
 rep(i,n)cin>>l[i];
 vector<int> v(n,0);
 dfs(0,v);
 cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
// #define int long long
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000               // 2e9
#define LLINF 2000000000000000000ll  // 2e18 (llmax:9e18)
#define fi first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define dmp(x) cerr << #x << ": " << x << endl;

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

template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
vector<T> vect(int len, T elem) {
  return vector<T>(len, elem);
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.fi << ',' << p.sec;
  return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.fi >> p.sec;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 < vec.size()) os << ' ';
  }
  return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) is >> vec[i];
  return is;
}
void fastio() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
}

#define endl "\n"

void solve() {
  string s;
  cin >> s;
  if(s.size()==2)cout << s << endl;
  else {
    reverse(all(s));
    cout << s << endl;
  }
  return;
}

signed main() {
  fastio();
  solve();
  // int t; cin >> t; while(t--)solve();
  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 N, M;
  cin >> N >> M;
  ll X[M];
  rep(i, M) cin >> X[i];
  sort(X, X+M);
  ll dif[M-1];
  rep(i, M-1) dif[i] = X[i+1] - X[i];
  sort(dif, dif + M -1);
  ll ans = 0;
  rep(i, M-N) ans += dif[i];
  cout << ans << endl;
  return 0;
}

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

int main() {
  int x,f=0;
  string ans="No";
  cin>>x;
  int tmp=x;
  while(tmp>0){
    f+=tmp%10;
    tmp/=10;
  }
  if(x%f==0){
    ans="Yes";
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main() {
    int x,a,b; 
    int d ,e;
    cin >> x >> a >> b;
    d = x - a;
    e = x - b;
    if(d<0){d = -d;}
    if(e<0){e = -e;}
    if(d<e){cout << "A";}
    else{cout << "B";}
    cout << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1000000007;

int main()
{

  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  double p[n];
  for(int i=0; i<n; i++){
    cin>>p[i];
  }
  double dp[n+1][n+1];
  memset(dp, 0.00, sizeof(dp));
  dp[0][0]=1.00;
  for(int i=1; i<=n; i++){
    for(int j=0; j<=i; j++){
        if(j==0){dp[i][j]=dp[i-1][j]*(1.00-p[i-1]);}
        else{
            dp[i][j]=dp[i-1][j]*(1.00-p[i-1])+dp[i-1][j-1]*p[i-1];
        }
    }
  }

  double ans=0.00;
  for(int i=(n+1)/2; i<=n; i++){
    ans=ans+dp[n][i];
  }
  cout<<fixed<<setprecision(10)<<ans;

  return 0;
}

Measured memory_bytes: 74152
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInteger = readLn :: IO Integer
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = do
	getLine
	as :: [Double] <- map fromIntegral <$> readInts
	let
		invsum = sum $ map ( 1 / ) as
	printf "%.10f\n" $ 1 / invsum

Measured memory_bytes: 508
import sys
sys.setrecursionlimit(10**9)


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, W = map(int, input().split())
    S = [list(input()) for i in range(H)]
    ans = 0
    memo_y = [[-1]*W for i in range(H)]
    memo_x = [[-1]*W for i in range(H)]
    for y in range(H):
        for x in range(W):
            c = 0
            if S[y][x] == '.':
                c += 1
                c_x = 0
                c_y = 0
                tmp_x = [x]
                tmp_y = [y]
                if memo_x[y][x] == -1:
                    for i in range(1, x+1):
                        if S[y][x-i] == '.':
                            c_x += 1
                            tmp_x.append(i)
                        else:
                            break
                    for i in range(x+1, W):
                        if S[y][i] == '.':
                            c_x += 1
                            tmp_x.append(i)
                        else:
                            break
                    for i in tmp_x:
                        memo_x[y][i] = c_x
                else:
                    c_x += memo_x[y][x]
                if memo_y[y][x] == -1:
                    for i in range(1, y+1):
                        if S[y-i][x] == '.':
                            c_y += 1
                            tmp_y.append(i)
                        else:
                            break
                    for i in range(y+1, H):
                        if S[i][x] == '.':
                            c_y += 1
                            tmp_y.append(i)
                        else:
                            break
                    for i in tmp_y:
                        memo_y[i][x] = c_y
                else:
                    c_y += memo_y[y][x]
                c += c_x + c_y
            ans = max(ans, c)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 248712
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author indy256
 */

#include <bits/stdc++.h>

using namespace std;

void solve(istream &in, ostream &out) {
    int n;
    in >> n;
    string s;
    in >> s;

    for (int i = 0; i < s.size(); ++i) {
        s[i] = (s[i] - 'A' + n) % 26 + 'A';
    }

    out << s << '\n';
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solve(in, out);
}


Measured memory_bytes: 256
N = int(input())
a = list(map(int, input().split()))
dict = {}
for i in range(N):
    if(a[i] in dict):
        dict[a[i]] += 1
    else:
        dict[a[i]] = 1
l = list(dict.keys())
ans = 0
for i in range(len(l)):
    if(dict[l[i]] >= l[i]):
        ans += dict[l[i]] - l[i]
    else:
        ans += dict[l[i]]
print(ans)

Measured memory_bytes: 18168
#include <stdio.h>

int main(void) {
  int x, y, r, temp;
  scanf("%d %d", &x, &y);

  if (x < y) {
    temp = x;
    x = y;
    y = temp;
  }

  while (y > 0) {
    r = x % y;
    x = y;
    y = r;
  }

  printf("%d\n", x);

  return 0;
}



Measured memory_bytes: 2140
N = int(input())
s = input()
R_cnt = [0] * (N + 1)
B_cnt = [0] * (N + 1)
G_cnt = [0] * (N + 1)
for i in range(N):
    if s[i] == 'R':
        R_cnt[i + 1] = R_cnt[i] + 1
        B_cnt[i + 1] = B_cnt[i]
        G_cnt[i + 1] = G_cnt[i]
    elif s[i] == 'B':
        R_cnt[i + 1] = R_cnt[i]
        B_cnt[i + 1] = B_cnt[i] + 1
        G_cnt[i + 1] = G_cnt[i]
    else:
        R_cnt[i + 1] = R_cnt[i]
        B_cnt[i + 1] = B_cnt[i]
        G_cnt[i + 1] = G_cnt[i] + 1
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if s[i] == s[j]:
            continue
            
        if s[i] == 'R' and s[j] == 'B' or s[i] == 'B' and s[j] == 'R':
            ans += G_cnt[N] - G_cnt[j]
        elif s[i] == 'B' and s[j] == 'G' or s[i] == 'G' and s[j] == 'B':
            ans += R_cnt[N] - R_cnt[j]
        elif s[i] == 'R' and s[j] == 'G' or s[i] == 'G' and s[j] == 'R':
            ans += B_cnt[N] - B_cnt[j]
        if j + (j - i) < N and s[i] != s[j] != s[j + (j - i)] != s[i]:
            ans -= 1
print(ans)


Measured memory_bytes: 69172
#include <stdio.h>

int horie_yui(int isikawa_kaito) {
	if (isikawa_kaito % 3 == 0) return 1;
	do {
		if (isikawa_kaito % 10 == 3) return 1;
	} while ((isikawa_kaito /= 10));
	return 0;
}

int main(void) {
	int n, i = 1;
	if (scanf("%d", &n) != 1) return 1;
	do {
		if (horie_yui(i)) printf(" %d", i);
	} while (++i <= n);
	putchar('\n');
	return 0;
}



Measured memory_bytes: 2136
#include<bits/stdc++.h>
using namespace std;
 
template <class T1, class T2>
ostream& operator << (ostream& out, const pair <T1, T2> p)
{
        out << '(' << p.first << ',' << p.second << ')';
            return out;
}
 
template <class T1, class T2>
istream& operator >> (istream& in, pair<T1, T2> &p)
{
        in >> p.first >> p.second;
            return in;
}
 
template <class T>
istream& operator >> (istream& in, vector<T> &v)
{
        for (T &x : v)
                    in >> x;
            return in;
}
 
template <class T>
ostream& operator << (ostream& out, const vector<vector<T> > &v)
{
        for (const vector<T> &x : v)
                    out << x << '\n';
            return out;
}
 
template <class T>
ostream& operator << (ostream& out, const vector<T> &v)
{
        for (const T &x : v)
                    out << x << ' ';
            return out;
}

template <class T>
ostream& operator << (ostream& out,const set<T> &s)
{
        for (const T &x : s)
                out << x << ' ';
            return out;
}
 
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll > ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define sz(x) (ll)(x).size()
#define tr1(x) cerr << #x << ": " << x << nl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << nl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<nl
#define tr4(x,y,z,w) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#w<<": "<<w<<nl
#define trv(a) cerr<<#a<<": ";for(ll zz=0;zz<sz(a);zz++) cerr<<a[zz]<<" ";cerr<<nl
#define trset(s) cerr<<#s<<": ";for(auto &i:s) cerr<<i<<" ";cerr<<nl
#define epsilon 0.00000001L
#define inf 9999999999999999ll// ~ 10^16
#define nl endl
#define all(x) x.begin(), x.end()
#define r_all(x) x.rbegin(), x.rend()
#define fast()  ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mod 1000000007ll
#define modulo 998244353ll
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}

vi fun(ll n,vi &a)
{
    //1st segment till i;
    vi ans(n+1);
    multiset <ll> s;
    ll sum=0;
    for(ll i=0;i<n;i++)
    {
        s.insert(a[i]);
        sum+=a[i];
        ans[0]=sum;
    }
    for(ll i=n;i<=2*n-1;i++)
    {
        sum+=a[i];
        s.insert(a[i]);
        sum-=*s.begin();
        s.erase(s.begin());
        ans[i-n+1]=sum;
    }
    return ans;
}
int main()
{
    fast();
    ll n;
    cin>>n;
    vi a(3*n);
    cin>>a;
    
    vi a1=fun(n,a);
    for(ll i=0;i<3*n;i++)
        a[i]*=-1;
    reverse(all(a));
    vi a2=fun(n,a);
    reverse(all(a2));
   // tr2(a1,a2);
    ll ans=-inf;
    for(ll i=0;i<sz(a1);i++)
        ans=max(ans,a1[i]+a2[i]);
    cout<<ans<<nl;
}


Measured memory_bytes: 11888
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

void insertionSort(int A[], int n, int g){
    for(int i=g;i<n;i++){
        int v=A[i];
        int j=i-g;
        while(j>=0&&A[j]>v){
            A[j+g]=A[j];
            j-=g;
            cnt++;
        }
        A[j+g]=v;
    }
}

void shellSort(int A[], int n){
    for(int h=1;;){
        if(h>n)break;
        G.push_back(h);
        h = 3*h+1;
    }
    for(int i=G.size()-1; i >=0;i--){
        insertionSort(A, n, G[i]);
    }
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++)scanf("%d", &A[i]);
    cnt=0;
    shellSort(A,n);
    cout << G.size() << endl;
    for(int i=G.size()-1;i>=0;i--){
        printf("%d", G[i]);
        if(i) printf(" ");
    }
    printf("\n");
    printf("%d\n", cnt);
    for(int i=0;i<n;i++)printf("%d\n", A[i]);

    return 0;
}

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

int main(){
  int N,a=0;
  cin >> N;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec.at(i);
  }
  sort(vec.begin(),vec.end());
  for(int i=0;i<N-1;i++){
    a+=vec.at(i);
  }
  if(vec.at(N-1)<a) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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

#define fi first
#define se second
#define pb push_back

typedef long long LL;
typedef long double LD;

const LL INF = (1LL << 60);

const int MAXN = 105;
bool floyd_warshall(int n, LL adjMat[MAXN][MAXN], int parent[MAXN][MAXN]);

int main() {

  ios_base::sync_with_stdio(0); cin.tie(0);

  int n, m;
  cin >> n >> m;

  LL adjMat[MAXN][MAXN]; int parent[MAXN][MAXN];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j)
        adjMat[i][j] = 0;
      else
        adjMat[i][j] = INF;
    }
  }

  for (int i = 0; i < m; i++) {
    int s, t; LL d;
    cin >> s >> t >> d;

    adjMat[s][t] = d;
  }

  bool has_negative_cycle = floyd_warshall(n, adjMat, parent);

  if (has_negative_cycle) {
    cout << "NEGATIVE CYCLE" << endl;
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (j > 0)
          cout << " ";
        if (adjMat[i][j] == INF)
          cout << "INF";
        else
          cout << adjMat[i][j];
      } cout << endl;
    }
  }

  return 0;
}

/*
 * @param n: number of nodes
 * @param adjMat[][]: adjacency matrix representation of the graph
 *                    mark adjMat[u][v] to INF if no edge exist between them
 * 
 * @return adjMat[u][v]: shortest path between u and v 
 * @return parent[u][v]: parent of v in shortest path u->v
 *
 * tested on 
 */
bool floyd_warshall(int n, LL adjMat[MAXN][MAXN], int parent[MAXN][MAXN]) {
  for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (adjMat[i][k] != INF && adjMat[k][j] != INF && adjMat[i][j] > adjMat[i][k] + adjMat[k][j])
            adjMat[i][j] = adjMat[i][k] + adjMat[k][j], parent[i][j] = parent[k][j];

  bool has_negative_cycle = false;
  for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (adjMat[i][k] != INF && adjMat[k][j] != INF && adjMat[i][j] > adjMat[i][k] + adjMat[k][j])
            has_negative_cycle = true;

  return has_negative_cycle;
}


Measured memory_bytes: 3284
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<stack>
#include<map>;
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
map<pair<int,int>,int> mp;
int cnt=1;
int head[maxn];
int degree[maxn];
int visited[maxn];
struct node
{
	int u,v,next;
}e[maxn];
void addedge(int u,int v)
{
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt++;
}
int main()
{
	int n;
	scanf("%d",&n);
	int cnt1=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			mp[make_pair(i,j)]=cnt1++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		int flag=mp[make_pair(min(i,x),max(i,x))];
		for(int j=2;j<=n-1;j++)
		{
			int y;
			scanf("%d",&y);
			addedge(flag,mp[make_pair(min(i,y),max(i,y))]);
			degree[mp[make_pair(min(i,y),max(i,y))]]++;
			flag=mp[make_pair(min(i,y),max(i,y))];
		}
	}
	queue<int> q;
	for(int i=1;i<=n*(n-1)/2;i++)
	{
		if(degree[i]==0)
		{
			q.push(i);
		}
	}
	int ans=0;
	while(!q.empty())
	{
		int sz=q.size();
		for(int i=1;i<=sz;i++)
		{
			int x=q.front();
			for(int j=head[x];j!=0;j=e[j].next)
			{
				int y=e[j].v;
				degree[y]--;
				if(degree[y]==0)
				{
					q.push(y);
				}
			}
			visited[x]=1;
			q.pop();
		}
		ans++;
	}
	int flag=1;
	for(int i=1;i<=n*(n-1)/2;i++)
	{
		if(visited[i]==0)
		{
			flag=0;
			break;
		}
	}
	if(flag)
	{
		printf("%d\n",ans);
	}
	else
		printf("-1\n");
	return 0;
}

Measured memory_bytes: 54016
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    token.parse().ok().unwrap()
}

fn main() {
    let a: i64 = input();
    let b: i64 = input();
    let c: i64 = input();
    let x: i64 = input();
    let y: i64 = input();

    let mut ans = a * x + b * y;
    ans = std::cmp::min(ans, 2 * c * std::cmp::max(x, y));
    ans = std::cmp::min(
        ans,
        2 * c * std::cmp::min(x, y) + a * (x - std::cmp::min(x, y)) + b * (y - std::cmp::min(x, y)),
    );
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define vi vector<int>
#define pb push_back
#define INF 999999999


//??????
ll factmemo[25]={1};
ll fact(int n){
    if(factmemo[n]!=0)return factmemo[n];
    return factmemo[n] = n*fact(n-1);
}

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

    cout<<fact(n)<<endl;
}

Measured memory_bytes: 2976
using System;

namespace ColorfulTransceivers {
    class ConsoleInput {
        private string[] currentLine = null;
        private int currentCursor = 0;

        public string Get() {
            if (currentLine == null || currentCursor >= currentLine.Length) {
                currentLine = Console.ReadLine().Split(' ');
                currentCursor = 0;
            }
            var res = currentLine[currentCursor];
            currentCursor++;
            return res;
        }

        public int GetInt() {
            return int.Parse(Get());
        }

    }

    class Program {
        static ConsoleInput input = new ConsoleInput();

        static void Main(string[] args) {
            var a = input.GetInt();
            var b = input.GetInt();
            var c = input.GetInt();
            var d = input.GetInt();

            //  直接
            if (Math.Abs(a - c) <= d) {
                Console.WriteLine("Yes");
                return;
            }
            
            //  間接
            if(Math.Abs(a-b) <= d && Math.Abs(b-c) <= d) {
                Console.WriteLine("Yes");
            }
            else {
                Console.WriteLine("No");
            }
        }
    }
}


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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

#define REP(i, n) for(ll i = 0 ; i < n; i++)

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    string S,T;
    cin >> S >> T;

    ll count = 0;
    for(int i = 0 ; i < S.size(); i++ ){
        if( S[i] != T[i]) count++;
    }

    cout << count << endl;
}


Measured memory_bytes: 3916