Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Splitwise Problem - 1
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
#include <bits/stdc++.h> using namespace std; const int N = 1e6; int balance[N]; int main() { int i, n, m, u, v, w; cin >> n >> m; for(i=0; i<m; i++) { cin >> u >> v >> w; //u has to pay v an amount w balance[u] -= w; balance[v] += w; } multiset<int> S; for(i=0; i<n; i++) if(balance[i] != 0) S.insert(balance[i]); int count = 0; while(!S.empty()) { int poor = *S.begin(); S.erase(S.begin()); int rich = *S.rbegin(); S.erase(prev(S.end())); int amount = min(-poor, rich); count++; //poor pays amount "amount" to rich poor += amount; rich -= amount; if (poor) S.insert(poor); if (rich) S.insert(rich); } cout << count << endl; }
g++
3 2 0 1 100 1 2 50
Show compiler warnings
[
+
] Compiler args
[
-
]
Show input
Compilation time: 1.84 sec, absolute running time: 0.17 sec, cpu time: 0.08 sec, memory peak: 3 Mb, absolute service time: 2,02 sec
fork mode
|
history
|
discussion
2